随笔-72  评论-126  文章-0  trackbacks-0

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(!&& !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(!&& !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ǎ崽 阅读(335) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理