hdu1426 深搜水題

hdu1426 深搜水題

簡單深搜 關鍵是輸入格式問題

#include
#include
#include
using namespace std;


int line[15][15],row[15][15],mark[5][5][15],map[15][15],num;
int leap[100][3];
int dfs(int t)
{
int i;
int a=leap[t][1],b=leap[t][2];
for(i=1;i<=9;i++)
{
if(line[a][i]||row[b][i]||mark[a/3][b/3][i]) continue;
//printf("####\n");
line[a][i]=row[b][i]=mark[a/3][b/3][i]=1;
map[a][b]=i;
if(t==num)
{
return 1;
}
if(!dfs(t+1))
{line[a][i]=row[b][i]=mark[a/3][b/3][i]=0;
map[a][b]=0;}
else return 1;
}
return 0;
}
int main()
{
int a,i,j,d=1;
char p,str[5];
while(~scanf("%s",str))//注意這個輸入格式 用%c容易出錯
{
memset(mark,0,sizeof(mark));//標記小正方形是否出現過這個數
memset(line,0,sizeof(line));//標記每一行是否出現過這個數
memset(row,0,sizeof(row));//每一列
memset(map,0,sizeof(map));//宮格
int t=0;
num=0;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(!(i==0&&j==0)) scanf("%s",str);
p=str[0];
if(p>='1'&&p<='9')
{
map[i][j]=p-'0';
line[i][p-'0']=1;
row[j][p-'0']=1;
mark[i/3][j/3][p-'0']=1;
}
else
{
leap[++t][1]=i;//把所有需要填的數的橫縱坐標存在leap數組裡
leap[t][2]=j;
num++;
}
}
}
dfs(1);//深搜所有需要填的數
if(d!=1) printf("\n");
d++;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(j!=0) printf(" ");
printf("%d",map[i][j]);
}
printf("\n");
}
}
return 0;
}