fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int,int>
  4. char arr[1010][1010];
  5.  
  6. int vis[1010][1010];
  7. int dist[1010][1010];
  8.  
  9. int dr[]={1,0,-1,0};
  10. int dc[]={0,1,0,-1};
  11.  
  12. int n, m;
  13.  
  14. int safe(int x,int y)
  15. {
  16.   return x>=0 && y>=0 && x<n && y<m;
  17. }
  18.  
  19.  
  20. void bfs(int sx, int sy)
  21. {
  22. 	queue< pii >q;
  23. 	q.push(pii(sx,sy));
  24.  
  25.     vis[sx][sy]=1;
  26.     dist[sx][sy]=1;
  27.  
  28. 	while(!q.empty())
  29. 	{
  30. 		pii top=q.front();
  31. 		q.pop();
  32. 		for(int i=0; i<4; i++)
  33. 		{
  34. 			int a = top.first + dr[i];
  35. 			int b = top.second + dc[i];
  36.  
  37.             if(safe(a,b) && !dist[a][b] && (int)arr[a][b]!=(int)arr[top.first][top.second])
  38.             {
  39.                q.push(pii(a,b));
  40.                dist[a][b] = dist[top.first][top.second]+1;
  41.                vis[a][b]=1;
  42.             }
  43. 		}
  44. 	}
  45. }
  46.  
  47.  
  48. int main()
  49. {
  50.     ios::sync_with_stdio(false);
  51.     int tc;
  52.  
  53.     cin>>tc;
  54.     while(tc--)
  55.     {
  56.         cin>>n>>m;
  57.  
  58.         memset(arr,0,sizeof(arr));
  59.         memset(vis, 0, sizeof(vis));
  60.         memset(dist, 0, sizeof(dist));
  61.  
  62.         for(int i=0; i<n; i++)
  63.         {
  64.           cin>>arr[i];
  65.         }
  66.         bfs(0,0);
  67.         if(!vis[n-1][m-1])
  68.             cout<<"-1\n";
  69.         else
  70.             cout<<dist[n-1][m-1]<<endl;
  71.     }
  72.     return 0;
  73. }
  74.  
  75.  
Success #stdin #stdout 0s 24208KB
comments (?)
stdin
copy 
2
3 3
011
001
000
2 2
11
00
stdout
copy 
5
-1
https://ideone.com/KGV9ft
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!