fork(7) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SttVq6
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!