fork 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
stdin
Standard input is empty
stdout
Standard output is empty