fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit)
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. // debug section start
  24. void __print(int x) {cerr << x;}
  25. void __print(long x) {cerr << x;}
  26. void __print(long long x) {cerr << x;}
  27. void __print(unsigned x) {cerr << x;}
  28. void __print(unsigned long x) {cerr << x;}
  29. void __print(unsigned long long x) {cerr << x;}
  30. void __print(float x) {cerr << x;}
  31. void __print(double x) {cerr << x;}
  32. void __print(long double x) {cerr << x;}
  33. void __print(char x) {cerr << '\'' << x << '\'';}
  34. void __print(const char *x) {cerr << '\"' << x << '\"';}
  35. void __print(const string &x) {cerr << '\"' << x << '\"';}
  36. void __print(bool x) {cerr << (x ? "true" : "false");}
  37.  
  38. template<typename T, typename V>
  39. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  40. template<typename T>
  41. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  42. void _print() {cerr << "]\n";}
  43. template <typename T, typename... V>
  44. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  45. #ifndef ONLINE_JUDGE
  46. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  47. #else
  48. #define debug(x...)
  49. #endif
  50. // debug section closed
  51.  
  52. #define en "\n"
  53. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  54. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  55. #define sqr(n) (1LL*(n)*(n))
  56.  
  57. #define vag(a,b) ((a + b - 1)/b)
  58.  
  59. #define MAXN 2010
  60. #define inf 1e6+5
  61. const ll mod = 1000000007;
  62.  
  63. int n, m;
  64. string a[1001];
  65.  
  66. int dx[] = { -1, 1, 0, 0};
  67. int dy[] = {0, 0, -1, 1};
  68.  
  69. bool valid(int x, int y)
  70. {
  71.     if (x >= 0 && x < n &&  x >= 0 && y < m) return true;
  72.     return false;
  73. }
  74. void bfs(int x, int y)
  75. {
  76.     deque<pair<int, int>>dq;
  77.  
  78.     vector<vector<int>>dis(n, vector<int>(m, -1));
  79.  
  80.     dis[x][y] = 0;
  81.     dq.push_back({x, y});
  82.     while (!dq.empty())
  83.     {
  84.         x = dq.front().ft; y = dq.front().sn;
  85.         dq.pop_front();
  86.  
  87.         for (int i = 0; i < 4; i++) {
  88.             int tx = x + dx[i];
  89.             int ty = y + dy[i];
  90.  
  91.             if (!valid(tx, ty)) continue;
  92.  
  93.             if (a[x][y] != a[tx][ty]) {
  94.                 if (dis[tx][ty] != -1) continue;
  95.                 dis[tx][ty] = dis[x][y] + 1;
  96.                 dq.push_back({tx, ty});
  97.             }
  98.             else {
  99.                 if (dis[tx][ty] != -1 && dis[tx][ty] <= dis[x][y]) continue;
  100.                 dis[tx][ty] = dis[x][y];
  101.                 dq.push_front({tx, ty});
  102.             }
  103.  
  104.         }
  105.     }
  106.  
  107.     cout << dis[n - 1][m - 1] << en;
  108.  
  109. }
  110. void solve()
  111. {
  112.     cin >> n >> m;
  113.     for (int i = 0; i < n; i++) {
  114.         cin >> a[i];
  115.     }
  116.  
  117.     bfs(0, 0);
  118. }
  119. int main()
  120. {
  121.     IOS;
  122.     ll t;
  123.     t = 1;
  124.     cin >> t;
  125.  
  126.     int c = 0;
  127.     while ( t-- )
  128.     {
  129.         // cout<<"Case "<<++c<<": ";
  130.         solve();
  131.     }
  132.     return 0;
  133. }
Runtime error #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hSyCFe
problem KATHTHI, based on SPOJ submission 31793916 (CPP14), 2023-09-05 07:20:13
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!