fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. typedef long long ll;
  5. char a[1005][1005];
  6. int mp[1005][1005];
  7. int vis[1004][1005];
  8. int dist[1005][1005];
  9. int dx[4]={1,-1,0,0};
  10. int dy[4]={0,0,-1,1};
  11. int t,r,c;
  12. string s;
  13. int valid(int x,int y)
  14. {
  15.     if(x>=r || x<0 || y>=c || y<0)
  16.     {
  17.         return 0;
  18.     }
  19.     if(vis[x][y])
  20.         return 0;
  21.     return 1;
  22. }
  23.  
  24. int main()
  25. {
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(NULL);
  28.     deque<pair<int,pair<int,int> > >dq;
  29.     scanf("%d",&t);
  30.     //cin>>t;
  31.     for(int i=0;i<t;i++)
  32.     {
  33.         dq.clear();
  34.         scanf("%d %d",&r,&c);
  35.        // cout<<r<<" "<<c<<endl;
  36.       //  cin>>r>>c;
  37.         for(int i=0;i<r;i++){
  38.             for(int j=0;j<c;j++){
  39.                 vis[i][j]=0;
  40.                 //dist[i][j]=0;
  41.             }
  42.         }
  43.         for(int j=0;j<r;j++)
  44.         {
  45.             //for(int k=0;k<c;k++)
  46.             //{
  47.                 scanf("%s",a[j]);
  48.               //  cout<<"chars "<<a[j][k];
  49.                 //cin>>a[j][k];
  50.            // }
  51.         }
  52.         for(int j=0;j<r;j++)
  53.         {
  54.             for(int k=0;k<c;k++)
  55.             {
  56.              //   cout<<a[j][k]<<" ";
  57.             }
  58.             //cout<<endl;
  59.         }
  60.     dq.push_back({0,{0,0}});
  61.  
  62.     for(int i=0;i<r;i++)
  63.     {
  64.         for(int j=0;j<c;j++)
  65.         {
  66.             dist[i][j]=INT_MAX;
  67.         }
  68.     }
  69.  
  70.     dist[0][0]=0;
  71.     while(!dq.empty())
  72.     {
  73.         pair<int,pair<int,int> >p = dq.front();
  74.         dq.pop_front();
  75.         int x = p.first;
  76.         int y = p.second.first;
  77.         if(x==r-1 && y==c-1)
  78.         	break;
  79.         int wt = p.second.second;
  80.         vis[x][y]=1;
  81.         int X,Y;
  82.         for(int i=0;i<4;i++)
  83.         {
  84.             X = x+dx[i];
  85.             Y = y+dy[i];
  86.             if(valid(X,Y))
  87.             {
  88.                 if(a[X][Y]==a[x][y])
  89.                 {
  90.                     dq.push_front({X,{Y,wt}});
  91.                     dist[X][Y] = min(dist[X][Y],wt);
  92.                 }
  93.                 else
  94.                 {
  95.                     dq.push_back({X,{Y,wt+1}});
  96.                     dist[X][Y] = min(dist[X][Y],wt+1);
  97.                 }
  98.             }
  99.         }
  100.     }
  101.    // cout<<"reached"<<endl;
  102.         //bfs(r,c);
  103.      //   cout<<dist[r-1][c-1]-1<<"\n";
  104.         printf("%d\n",dist[r-1][c-1]);
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 28056KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/h4CWcZ
language:
C++14 (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!