dfs 一行一行来

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

const int dx[9]={0,0,0,1,-1,1,1,-1,-1};

const int dy[9]={0,1,-1,0,0,-1,1,1,-1};

int visit[15][15];//表示需要填的数目；

int ans[15][15];//答案；

int n,m,flag=0;

int around(int x,int y)

{

   int res=0;

   for(int i=0;i<=8;i++){

      int nx=x+dx[i],ny=y+dy[i];

      if(nx<=0||ny<=0||nx>n||ny>m||ans[nx][ny]==0) continue;

      res++;

   }

   return res;

} 

bool check(int x,int y){//x是行数，y是列数，不要和坐标系里面的东西混淆了！ 

if(visit[x][y]==-1) return true;

if(around(x,y)==visit[x][y]) return true;

return false;

}

void dfs(int x,int y){

if(x==n+1){

for(int i=max(1,n-1);i<=n;i++){

for(int j=1;j<=m;j++){

if(!check(i,j))  return;

} 

}

flag=1;

return;

}

if(y==m){

if(!flag)ans[x][y]=0;//默认填0；

  if(x==1||(check(x-1,y)&&(y==1||check(x-1,y-1)))){//第一行可以直接下去

     if(!flag) dfs(x+1,1);

        }

        //不行，那就。

if(!flag)ans[x][y]=1;

        if(x==1||(check(x-1,y)&&(y==1||check(x-1,y-1)))){//第一行可以直接下去

     if(!flag) dfs(x+1,1);

        }

        return;

}

      if(!flag)ans[x][y]=0;//默认填0；

if(y==1||x==1||check(x-1,y-1)){//第一列可以直接向右移动 

     if(!flag) dfs(x,y+1);

        }

        //不行，那就。

if(!flag)ans[x][y]=1;

        if(y==1||x==1||check(x-1,y-1)){//第一行可以直接下去

     if(!flag) dfs(x,y+1);

        }

}

int main(){

cin>>n>>m;

for(int i=1;i<=n;i++){

char ch;

for(int j=1;j<=m;j++){

cin>>ch;

if(ch=='_') visit[i][j]=-1;

else visit[i][j]=ch-'0';

}

}

dfs(1,1);

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++)

cout<<ans[i][j];

cout<<endl;

}

}