http://acm.hdu.edu.cn/showproblem.php?pid=1426
本来以为可以构造
位运算加模拟，以为可以写的很飘逸。。。
不过函数写的太简单，很多数据构造不出来
#include<stdio.h>
#include<string>
int hash[28];
char map[9][10];
int cnt;
void add(int id,char ch)
{
if(ch=='?')
{
cnt ++;
return ;
}
hash[id] += 1<<(ch-'0'-1);
}
int onlyone(int key)
{
switch (key)
{
case 510:
return 1;
case 509:
return 2;
case 507:
return 3;
case 503:
return 4;
case 495:
return 5;
case 479:
return 6;
case 447:
return 7;
case 383:
return 8;
case 255:
return 9;
}
return -1;
}
bool hh(int i,int j)
{
int key,pos;
key = hash[i] | hash[j+9] | hash[(i/3)*3+(j/3)+18];
pos = onlyone(key);
if(pos==-1)
return false;
map[i][j] = pos+'0';
pos --;
hash[i] += 1<<pos;
hash[j+9] += 1<<pos;
hash[(i/3)*3+(j/3)+18] += 1<<pos;
return true;
}
int main()
{
int i,j;
char ch;
while(scanf("%c",&ch)==1)
{
cnt = 0;
memset(hash,0,sizeof(hash));
add(0,ch);
add(9,ch);
add(18,ch);
map[0][0] = ch;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(!i && !j)
continue;
while((ch=getchar())==' ' || ch=='\n');
add(i,ch);
add(j+9,ch);
add((i/3)*3 + (j/3) + 18,ch);
map[i][j] = ch;
}
map[i][j] = 0;
}
cnt /= 3;
while(cnt)
{
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(map[i][j]=='?' && hh(i,j))
cnt --;
}
}
for(i=0;i<9;i++)
{
for(j=0;j<8;j++)
printf("%c ",map[i][j]);
printf("%c\n",map[i][8]);
}
}
return 0;
}
很多数据出不来，会导致TLE，
据说有人写了1000多行代码构造出数独。拿了什么的一等奖。。。
最后只能傻傻的写写dfs了。。唉。。
效率不行
在新服务器上交都还拿不了第一。。。
#include<stdio.h>
#include<string>
int hash[28];
char map[9][10];
int cnt;
bool flag;
void add(int id,char ch)
{
hash[id] += 1<<(ch-'0'-1);
}
void dfs()
{
int i,j,key,pos,k;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(map[i][j]=='?')
{
k = (i/3)*3+(j/3)+18;
key = hash[i] | hash[j+9] | hash[k];
if(key==511)
return ;
for(pos=1;pos<=9;pos++)
{
if(!(key&1))
{
map[i][j] = pos +'0';
pos --;
hash[i] += 1<<pos;
hash[j+9] += 1<<pos;
hash[k] += 1<<pos;
cnt --;
if(cnt==0)
{
flag =true;
return ;
}
dfs();
if(flag)
return ;
map[i][j] = '?';
hash[i] -= 1<<pos;
hash[j+9] -= 1<<pos;
hash[k] -= 1<<pos;
pos ++;
cnt ++;
}
key >>= 1;
}
return ;
}
}
}
}
int main()
{
int i,j;
char ch;
bool x=false;
while(scanf("%c",&ch)==1)
{
if(x)
puts("");
x = true;
cnt = 0;
memset(hash,0,sizeof(hash));
if(ch=='?')
cnt ++;
else
{
add(0,ch);
add(9,ch);
add(18,ch);
}
map[0][0] = ch;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(!i && !j)
continue;
while((ch=getchar())==' ' || ch=='\n');
if(ch=='?')
cnt ++;
else
{
add(i,ch);
add(j+9,ch);
add((i/3)*3 + (j/3) + 18,ch);
}
map[i][j] = ch;
}
map[i][j] = 0;
}
flag = false;
dfs();
for(i=0;i<9;i++)
{
for(j=0;j<8;j++)
printf("%c ",map[i][j]);
printf("%c\n",map[i][8]);
}
getchar();
getchar();
}
return 0;
}
posted on 2009-03-08 00:53
shǎ崽 阅读(289)
评论(0) 编辑 收藏 引用