codevs 1049 棋盘染色

#include<bits/stdc++.h> using namespace std; int map1[10][10]; int map2[10][10]; int deep,ans,flag; int dir[4][2]={-1,0,0,1,1,0,0,-1}; void dfs1(int x,int y) { if(map2[x][y]==1) map2[x][y]=-1; else return; for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; dfs1(xx,yy); } } void jiancha() { ans=0; for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) map2[i][j]=map1[i][j]; } for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) { if(map2[i][j]==1) { ans++; dfs1(i,j); } } } } void dfs(int x,int y,int step) { if(step==deep) { jiancha(); if(ans==1) { flag=1; } return; } for(int j=y;j<=5;j++) { if(map1[x][j]) continue; else { map1[x][j]=1; //cout<<1<<endl; dfs(x,j,step+1); map1[x][j]=0; } } for(int i=x+1;i<=5;i++) { for(int j=1;j<=5;j++) { if(map1[i][j]) continue; else { map1[i][j]=1; if(j==5) dfs(i+1,1,step+1); else dfs(i,j,step+1); map1[i][j]=0; } } } } int main() { int n,m; char str[10]; for(int i=1;i<=5;i++) { scanf("%s",str); for(int j=1;j<=5;j++) { map1[i][j]=str[j-1]-'0'; } } for(int i=0;i<=25;i++) { deep=i; dfs(1,1,0); if(flag) break; } cout<<deep<<endl; return 0; }