fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define Samurai ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  5. #define pr_g priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>
  6. int dx [] = {0, 0, 1, -1, 1, 1, -1, -1};
  7. int dy [] = {-1, 1, 0, 0, -1, 1, 1, -1};
  8. char dir [] = {'>', '<', '^', 'v'};
  9. int Lx[] = {2, 2, -2, -2, 1, 1, -1, -1};
  10. int Ly[] = {1, -1, 1, -1, 2, -2, 2, -2};
  11. const double PI = acos(-1.0);
  12. #define el '\n'
  13. const ll mod = 1e9 + 7, N = 1e3 + 5, OO = 0x3f3f3f3f;
  14.  
  15. void solve() {
  16.     int R, C; cin >> R >> C;
  17.  
  18.     char A[R][C];
  19.     for (int i = 0; i < R; i++)
  20.         for (int j = 0; j < C; j++)
  21.             cin >> A[i][j];
  22.  
  23.     int vis[R][C];
  24.     memset(vis, OO, sizeof vis);
  25.     deque<pair<int,int>> q;
  26.     q.push_back({0,0});
  27.     vis[0][0] = 0;
  28.     while (q.size()) {
  29.         int a = q.front().first;
  30.         int b = q.front().second;
  31.         q.pop_front();
  32.         if (a == R - 1 && b == C - 1) {
  33.             cout << vis[a][b] << el;
  34.             return;
  35.         }
  36.  
  37.         for (int i = 0; i < 4; i++) {
  38.             int x = a + dx[i];
  39.             int y = b + dy[i];
  40.             if (x >= 0 && x < R && y >= 0 && y < C) {
  41.                 int u = vis[a][b] + (A[a][b] != A[x][y]);
  42.                 if (vis[x][y] <= u)
  43.                     continue;
  44.                 vis[x][y] = u;
  45.                 if (A[x][y] == A[a][b])
  46.                     q.push_front({x,y});
  47.                 else
  48.                     q.push_back({x,y});
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. int main() { Samurai
  55.     int _t = 1; cin >> _t;
  56.     for (int i = 1; i <= _t; i++){
  57.         solve();
  58.     }
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/TWr8he
language:
C++ (gcc 8.3)
created:
3 days 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!