Advertisement
Helicator

Map.cpp

Jan 17th, 2022
505
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define vi vector<int>
  6. #define vii vector<vi>
  7. #define ii pair<int,int>
  8. #define fi first
  9. #define sc second
  10. #define pb push_back
  11. #define stoi stoll
  12. #define popcnt __builtin_popcount
  13. #define getbit(x, k) ((x >> k) & 1)
  14. #define all(x) (x).begin(),(x).end()
  15. #define FOR(i,j,k) for(int i=j; i<(int)k; ++i)
  16. #define look(a) cerr <<#a<<": "<<a<<endl;
  17. #define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;
  18.  
  19. struct Node
  20. {
  21.     int x;
  22.     int y;
  23. };
  24.  
  25. struct queueNode
  26. {
  27.     Node p;
  28.     int count;
  29. };
  30.  
  31. int n,m;
  32. Node c,d;
  33.  
  34. bool valid(int x, int y)
  35. {
  36.     return x >= 0 && x < n &&
  37.            y >= 0 && y < m;
  38. }
  39.  
  40. int BFS(vii a, Node c, Node d)
  41. {
  42.     bool v[n][m];
  43.     memset(v,0,sizeof(v));
  44.     v[c.x][c.y] = true;
  45.  
  46.     queue<queueNode> q;
  47.     queueNode s = {c,-1};
  48.     q.push(s);
  49.     while(!q.empty())
  50.     {
  51.         queueNode curr = q.front();
  52.         Node pt = curr.p;
  53.  
  54.         if (pt.x == d.x && pt.y == d.y)
  55.             return curr.count;
  56.  
  57.         q.pop();
  58.  
  59.         int i;
  60.  
  61.         i = pt.x-1;
  62.         while (valid(i,pt.y) && a[i][pt.y] && !v[i][pt.y]) --i;
  63.         for (int j = pt.x-1; j > i; --j){
  64.                 v[j][pt.y] = true;
  65.                 queueNode next = {{j,pt.y},curr.count+1};
  66.                 q.push(next);
  67.             }
  68.  
  69.         i = pt.x+1;
  70.         while (valid(i,pt.y) && a[i][pt.y] && !v[i][pt.y]) ++i;
  71.         for (int j = pt.x+1; j < i; ++j){
  72.                 v[j][pt.y] = true;
  73.                 queueNode next = {{j,pt.y},curr.count+1};
  74.                 q.push(next);
  75.             }
  76.  
  77.         i = pt.y-1;
  78.         while (valid(pt.x,i) && a[pt.x][i] && !v[pt.x][i]) --i;
  79.         for (int j = pt.y-1; j > i; --j){
  80.                 v[pt.x][j] = true;
  81.                 queueNode next = {{pt.x,j},curr.count+1};
  82.                 q.push(next);
  83.             }
  84.  
  85.         i = pt.y+1;
  86.         while (valid(pt.x,i) && a[pt.x][i] && !v[pt.x][i]) ++i;
  87.         for (int j = pt.y+1; j < i; ++j){
  88.                 v[pt.x][j] = true;
  89.                 queueNode next = {{pt.x,j},curr.count+1};
  90.                 q.push(next);
  91.             }
  92.     }
  93.     return -1;
  94. }
  95.  
  96. void solve()
  97. {
  98.     cin >> n >> m;
  99.     vii a(n,vi(m,0));
  100.     FOR(i,0,n){
  101.         string x;
  102.         cin >> x;
  103.         FOR(j,0,m){
  104.             a[i][j] = (x[j] == '#') ? 0 : 1;
  105.             if(x[j] == 'C'){
  106.                 c.x = i;
  107.                 c.y = j;
  108.             }
  109.             if(x[j] == 'N'){
  110.                 d.x = i;
  111.                 d.y = j;
  112.             }
  113.         }
  114.     }
  115.     int ans = BFS(a,c,d);
  116.  
  117.     FOR(i,0,n)
  118.    
  119.  
  120.     cout << ans;
  121. }
  122.  
  123. signed main()
  124. {
  125.     cin.tie(0)->sync_with_stdio(0);
  126.     // freopen("in", "r", stdin);
  127.     // freopen("out", "w", stdout);
  128.     solve();
  129. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement