洛谷01迷宮(P 141)の2つの解法--dfsとbfs

数字の0と1だけからなるnがあります×n格迷宮.グリッド0に位置すると、隣接する4つのグリッドの1つに移動できます.同じように、グリッド1に位置すると、隣接する4つのグリッドの0に移動できます.あなたの任務は、与えられた迷路について、あるグリッドからどれだけの格子(自分を含む)に移動できるかを尋ねることです.フォーマット第1の動作の2つの正の整数n,mを入力します.次のn行、各行n文字、文字は0または1のみで、文字間にスペースはありません.次にm行、各行2個をスペースで区切った正の整数i,jは、迷宮のiii行目jj列目の格子に対応し、この格子からどれだけの格子に移動できるかを尋ねる.出力フォーマットm行は、質問ごとに対応する答えを出力します.タイトルリンクの下にはコードがあります.

/* dfs +       */
#include
using namespace std;
char maze[1010][1010];  //    
int book[1010][1010] , n , m , walk[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};  //book      
int ans[100001];//    
void dfs(int x , int y , int num)   //x，y     ，num      
{
   for(int i = 0 ; i < 4 ; i++){
    int dx = x + walk[i][0];
    int dy = y + walk[i][1];
      if(book[dx][dy] == 0)
      if(maze[x-1][y-1] != maze[dx-1][dy-1] && dx > 0 && dy > 0 && dx <= n && dy <= n){
         book[dx][dy] = num;   //         ，         ，          
         ans[num]++;        //      
         dfs(dx , dy , num);
     }
   }
}
int main()
{
   //freopen("P1141_2.in","r",stdin);
   int x , y;
   cin>>n>>m;
   for(int i = 0 ; i < n ; i++)
       scanf("%s",&maze[i]);
    for(int i = 1 ; i <= m ; i++){
        scanf("%d%d",&x,&y);
        if(book[x][y] == 0)dfs( x , y , i );  //         ，   dfs
        else ans[i] = ans[book[x][y]];       //      ，        
        printf("%d
",ans[i]);
    }
    return 0;
}
/* bfs +       */
#include
using namespace std;
char Map[1001][1001];   //    
int book[1001][1001] , ans[100001] , n , m , xi , yi , walk[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};  //    book   dfs book           
struct node{             //       
    int x , y;
};
queue<node>q;node nd;   //  
void bfs(int x , int y , int num)  //num      
{
 nd.x = x;    
 nd.y = y;
 ans[num]++;
 book[x][y] = num;
 q.push(nd);   //   
  while(!q.empty()){       //       
    nd = q.front();      //       
    for(int i = 0 ; i < 4 ; i++){       //      
    node nnode = nd;
    nnode.x = nd.x + walk[i][0];
    nnode.y = nd.y + walk[i][1];
      if(book[nnode.x][nnode.y] == 0 && nnode.x > 0 && nnode.y > 0 && nnode.x <= n && nnode.y <= n && Map[nd.x-1][nd.y-1] != Map[nnode.x-1][nnode.y-1]){ //      
      q.push(nnode);  //  
      ans[num]++;    // n     
      book[nnode.x][nnode.y] = num;   //       
      }
    }
    q.pop();  //      
  }
}
int main()
{
   cin>>n>>m;
    for(int i = 0 ; i < n ; i++)
        scanf("%s",&Map[i]);
     for(int i = 1 ; i <= m ; i++){
      scanf("%d%d",&xi,&yi);
       if(book[xi][yi] == 0){
        bfs(xi , yi , i);
       }
       else ans[i] = ans[book[xi][yi]];
        printf("%d
" , ans[i]);
     }
   return 0;
}