fork(12) download
copy 
  1. #include<stdio.h>
  2.  
  3. int dx[] = {1,-1,0,0};
  4. int dy[] = {0,0,1,-1}; 
  5. int n,m,sx,sy,xx,yy,visited[1001][1001];
  6. char Cell[1001][1001];
  7.  
  8. int isSafe(int x, int y)
  9. {
  10.     return (x>=0 && y>=0 && x<n && y<m && visited[x][y]==0 && (Cell[x][y] == 'b' || Cell[x][y] == 'f') );
  11. }
  12.  
  13. int Dfs(int x,int y)
  14. {
  15.     //printf("%d %d\n",x,y);
  16.     //visited[x][y] = 1;
  17.     if(Cell[x][y] == 'f')  return 1;
  18.     for(int dir=0; dir<4; dir++)
  19.     {
  20.         xx = x+dx[dir];  yy = y+dy[dir];
  21.         if( isSafe(xx,yy) )  
  22.         {  
  23.             visited[x][y] = 1;  
  24.             if( Dfs(xx,yy) )   {  Cell[x][y] = 'x';  return 1;  }
  25.  
  26.         }   
  27.     }    
  28.     return 0;
  29. }
  30.  
  31. int main() 
  32. { 
  33.     int i,j,T;
  34.     scanf("%d",&T);
  35.     while(T--)
  36.     {
  37.        scanf("%d%d",&n,&m);
  38.        for(i=0; i<n; i++)
  39.          for(j=0; j<m; j++)
  40.               visited[i][j] = 0;
  41.  
  42.         for(i=0; i<n; i++)  scanf("%s",Cell[i]);
  43.  
  44.         for(i=0; i<n; i++)
  45.          for(j=0; j<m; j++)
  46.             if(Cell[i][j] == 's')  {  sx=i,sy=j;  break;  }
  47.  
  48.         if(Dfs(sx,sy))
  49.         {
  50.            for(i=0; i<n; i++)
  51.            {
  52.               for(j=0; j<m;j++)
  53.                {  
  54.                    if( Cell[i][j] == 'x')  Cell[i][j] = 'b' ;
  55.                    else if( Cell[i][j] == 'w' || Cell[i][j] == 'b' )  Cell[i][j] = '-' ;
  56.                }
  57.            }
  58.           Cell[sx][sy] = 's'; 
  59.           for(i=0; i<n; i++)  printf("%s\n",Cell[i]);
  60.         }
  61.         else  printf("The path doesn't exist.\n");
  62.     }
  63.   return 0;
  64. }
Success #stdin #stdout 0s 7748KB
comments (?)
stdin
copy 
2
6 5
bbbbw
bwwfw
bbbww
bwwww
bbbbw
wwwbs

4 4
bbbw
wwfw
bwww
bbbs
stdout
copy 
bbbb-
b--f-
b----
b----
bbbb-
---bs
The path doesn't exist.
https://ideone.com/jIeDBy
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!