fork(5) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int LL;
  5.  
  6. #define inp_s ios_base::sync_with_stdio(false)
  7. #define DRT() int test_case;cin>>test_case;while(test_case--)
  8.  
  9. #define VI vector<int>
  10. #define VS vector<string>
  11. #define VLL vector<LL>
  12. #define PII pair<int,int>
  13. #define all(c) c.begin(),c.end()
  14. #define sz(c) c.size()
  15. #define clr(c) c.clear()
  16. #define msi map<string,int>
  17. #define msit map<string,int>::iterator
  18. #define pb push_back
  19. #define mp make_pair
  20.  
  21. #define GI(x) scanf("%d",&x)
  22.  
  23. #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  24. #define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
  25.  
  26. #define gcd(a,b) __gcd(a,b)
  27. #define MOD 1000000007
  28. #define EPS 1E-10
  29. #define ELR 2.71828182845904523536
  30. #define PI acos(-1)
  31.  
  32. #define CASE(x) cout << "Case #" << x << ": "
  33.  
  34. int poss(int a,int b,int c,int d)
  35. {
  36. if(a >= 0 && a< c && b >=0 && b < d) return 1;
  37. else return 0;
  38. }
  39.  
  40. int main()
  41. {
  42. inp_s;
  43. DRT()
  44. {
  45. int n,m;
  46. cin >> n >> m;
  47. vector<string> arr(n);
  48. FOR(i,0,n) cin >> arr[i];
  49.  
  50. deque< PII > bfs;
  51. int visited[n][m];
  52. FOR(i,0,n) FOR(j,0,m) visited[i][j] = INT_MAX;
  53. visited[0][0] = 1;
  54. bfs.push_front(mp(0,0));
  55.  
  56. int dx[] = {1,-1,0,0};
  57. int dy[] = {0,0,1,-1};
  58.  
  59. while(!bfs.empty())
  60. {
  61. PII node = bfs.front();
  62. bfs.pop_front();
  63.  
  64. if(node.first == n-1 && node.second == m-1) break;
  65.  
  66. FOR(i,0,4)
  67. {
  68. int x = node.first + dx[i];
  69. int y = node.second + dy[i];
  70.  
  71. if(poss(x,y,n,m))
  72. {
  73. if(arr[x][y] == arr[node.first][node.second] && visited[x][y] > visited[node.first][node.second])
  74. {
  75. visited[x][y] = visited[node.first][node.second];
  76. bfs.push_front(mp(x,y));
  77. }
  78. else if(visited[x][y] > visited[node.first][node.second] + 1)
  79. {
  80. visited[x][y] = visited[node.first][node.second] + 1;
  81. bfs.push_back(mp(x,y));
  82. }
  83. }
  84. }
  85. }
  86. cout << visited[n-1][m-1] - 1 << endl;
  87. }
  88. return 0;
  89. }
  90.  
Time limit exceeded #stdin #stdout 5s 528384KB
stdin
Standard input is empty
stdout
Standard output is empty