fork download 
  1. /****************************************************
  2.  * Author  : duc viet
  3.  * From    : HSGS Tran Phu, Hai Phong
  4.  * Created : 2026-11-03 10:47:53
  5.  ****************************************************/
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define                        LOCAL
  11. #define                       fi first
  12. #define                       se second
  13. #define                      left ___left
  14. #define                      right ___right
  15. #define                      int long long
  16. #define           TIME  (1.0 * clock() / CLOCKS_PER_SEC)
  17. #define                    MASK(i)  (1LL << (i))
  18. #define                 BIT(x, i)  ((x) >> (i) & 1)
  19. #define          __builtin_popcount  __builtin_popcountll
  20. #define                 ALL(v)  (v).begin(), (v).end()
  21. #define              REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
  22. #define             REPD(i, n)  for (int i = (n); i-- > 0; )
  23. #define             FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i)
  24. #define          FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; )
  25. #define            FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
  26. #define         FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
  27. #define             scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
  28. #define            print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
  29.  
  30. template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
  31. template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
  32. template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
  33. template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
  34. template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
  35. template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
  36.  
  37. #ifdef LOCAL
  38.     // #include "debug.h"
  39. #else
  40.     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  41.     #define DB(...) 23
  42.     #define db(...) 23
  43.     #define debug(...) 23
  44. #endif
  45.  
  46.  
  47. const int N = 1e6 + 5;
  48. const int mod = 1e9 + 7;
  49.  
  50.  
  51. char grid[1010][1010];
  52. int d[1010][1010];
  53.  
  54. int dx[4] = {1, -1, 0, 0};
  55. int dy[4] = {0, 0, 1, -1};
  56.  
  57. int n, m, q;
  58.  
  59.  
  60. void bfs() {
  61.     deque<pair<int, int>> dq;
  62.  
  63.     for (int i = 1 ; i <= m; i++) {
  64.         for (int j = 1; j <= n; j++) {
  65.             if (grid[i][j] == '*') {
  66.                 d[i][j] = 0;
  67.                 dq.push_back({i, j});
  68.             }
  69.             else d[i][j] = LLONG_MAX;
  70.         }
  71.     }
  72.  
  73.     while (!dq.empty()) {
  74.         pair<int, int> p = dq.front(); dq.pop_front(); 
  75.  
  76.         int x = p.first;
  77.         int y = p.second;
  78.  
  79.         for (int i = 0; i < 4; i++) {
  80.             int xi = x + dx[i];
  81.             int yi = y + dy[i];
  82.  
  83.             if (xi < 1 || xi > m || yi < 1 || yi > n) continue; 
  84.  
  85.             int w;
  86.             if (grid[xi][yi] != grid[x][y]) w = 1;
  87.             else w = 0;
  88.  
  89.             if (d[x][y] + w < d[xi][yi]) {
  90.                 d[xi][yi] = d[x][y] + w;
  91.  
  92.                 if (w == 0) dq.push_front({xi, yi});
  93.                 else dq.push_back({xi, yi}); 
  94.             }
  95.         }
  96.     }
  97. }
  98.  
  99.  
  100. void Solve(){
  101.     cin >> m >> n >> q; 
  102.  
  103.     for (int i = 1; i <= m; i++) cin >> (grid[i] + 1);
  104.     bfs();
  105.  
  106.     while (q--) {
  107.         int x, y ; cin >> x >> y;
  108.  
  109.         cout << d[x][y] << endl; 
  110.     }
  111. }
  112.  
  113.  
  114. signed main(){
  115.     ios::sync_with_stdio(false);
  116.     cin.tie(nullptr);
  117.  
  118.     // file(ILOVEHD);
  119.  
  120.     Solve();
  121.  
  122.     #ifdef LOCAL
  123.         cerr << "\n-------------------\n";
  124.         cerr << "Time elapsed: " << TIME << " s\n";
  125.     #endif
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin 
4 5 4 
*ACCB 
AACCB 
AACBA 
AAAAA 
3 5 
1 5 
3 3 
2 4
stdout 
1
2
2
2
stderr 
-------------------
Time elapsed: 0.004368 s
https://ideone.com/xVJat7
language:
C++14 (gcc 8.3)
created:
16 hours 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!