首页 > 代码库 > POJ 2918 Tudoku [搜索]
POJ 2918 Tudoku [搜索]
和POJ2676一样哈,,,
原谅我水题目数 = =!。。。
#include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> using namespace std; int map[10][10]; char tmp[10][10]; bool row[10][10]; bool col[10][10]; bool grid[10][10]; bool DFS(int x,int y) { int here=3*((x-1)/3)+(y-1)/3+1; if(x==10) return true; if(map[x][y]) { bool flag; return y==9?flag=DFS(x+1,1):flag=DFS(x,y+1); } else { for(int num=1;num<=9;num++) { if(!row[x][num]&&!col[y][num]&&!grid[here][num]) { map[x][y]=num; row[x][num]=true; col[y][num]=true; grid[here][num]=true; bool flag; y==9?flag=DFS(x+1,1):flag=DFS(x,y+1); if(flag) return true; else { map[x][y]=0; row[x][num]=false; col[y][num]=false; grid[here][num]=false; } } } } return false; } int main() { //freopen("/home/rainto96/in.txt","r",stdin); int test; cin>>test; for(int times=1;times<=test;times++) { memset(map,0,sizeof(map)); memset(tmp,0,sizeof(tmp)); memset(grid,0,sizeof(grid)); memset(col,0,sizeof(col)); memset(row,0,sizeof(row)); for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { cin>>tmp[i][j]; int here=3*((i-1)/3)+(j-1)/3+1; map[i][j]=tmp[i][j]-'0'; if(map[i][j]) { row[i][map[i][j]]=true; col[j][map[i][j]]=true; grid[here][map[i][j]]=true; } } } DFS(1,1); cout<<"Scenario #"<<times<<":\n"; for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { cout<<map[i][j]; } cout<<'\n'; } cout<<'\n'; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。