Advertisement
mickypinata

USACO-T036: Overfencing

Dec 16th, 2021
641
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: maze1
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define f first
  11. #define s second
  12. typedef pair<int, int> pii;
  13. typedef pair<pii, int> ppi;
  14.  
  15. const pii dir[4] = {pii(0, 1), pii(0, -1), pii(1, 0), pii(-1, 0)};
  16. const int R = 200 + 5;
  17. const int C = 76 + 5;
  18.  
  19. int row, col;
  20. char board[R][C];
  21. bool visited[R][C];
  22.  
  23. bool isInBoard(const pii &x){
  24.     return 2 <= x.f && x.f <= row && 2 <= x.s && x.s <= col;
  25. }
  26.  
  27. int main(){
  28.     freopen("maze1.in", "r", stdin);
  29.     freopen("maze1.out", "w", stdout);
  30.  
  31.     scanf("%d%d%*c", &col, &row);
  32.     row *= 2;
  33.     col *= 2;
  34.     for(int i = 1; i <= row + 1; ++i){
  35.         for(int j = 1; j <= col + 1; ++j){
  36.             scanf("%c", &board[i][j]);
  37.         }
  38.         scanf("%*c");
  39.     }
  40.     queue<ppi> que;
  41.     for(int i = 2; i <= row; i += 2){
  42.         visited[i][0] = true;
  43.         que.emplace(pii(i, 0), 0);
  44.         visited[i][col + 2] = true;
  45.         que.emplace(pii(i, col + 2), 0);
  46.     }
  47.     for(int j = 2; j <= col; j += 2){
  48.         visited[0][j] = true;
  49.         que.emplace(pii(0, j), 0);
  50.         visited[row + 2][j] = true;
  51.         que.emplace(pii(row + 2, j), 0);
  52.     }
  53.     int mx = 0;
  54.     while(!que.empty()){
  55.         pii u = que.front().f;
  56.         int dt = que.front().s;
  57.         que.pop();
  58.         mx = max(mx, dt);
  59.         for(int d = 0; d < 4; ++d){
  60.             pii obs = pii(u.f + dir[d].f, u.s + dir[d].s);
  61.             pii v = pii(u.f + 2 * dir[d].f, u.s + 2 * dir[d].s);
  62.             if(isInBoard(v) && board[obs.f][obs.s] == ' ' && !visited[v.f][v.s]){
  63.                 visited[v.f][v.s] = true;
  64.                 que.emplace(v, dt + 1);
  65.             }
  66.         }
  67.     }
  68.     cout << mx << '\n';
  69.  
  70.     fclose(stdin);
  71.     fclose(stdout);
  72.     return 0;
  73. }
  74.  
Advertisement
RAW Paste Data Copied
Advertisement