fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int N;
  10. bool isMove = false;
  11.  
  12. struct con{
  13.     int r;
  14.     int c;
  15.     int ct;
  16.     int chk;
  17. };
  18.  
  19. int rl[8] = {0, 0, 1, -1, 1, 1, -1, -1};
  20. int ud[8] = {1, -1, 0, 0, 1, -1, 1, -1};
  21.  
  22. vector<vector<int>> mat;
  23. vector<vector<int>> paddler;
  24.  
  25. bool visited[52][52][2];
  26.  
  27.     //1 -> vertical
  28.     //0 -> hortizental
  29.  
  30. bool isRotate(int row, int col){
  31.     bool isTree = true;
  32.     for (int i = 0; i < 8; i++)
  33.     {
  34.         if (mat[row + ud[i]][col + rl[i]] == 1)
  35.         {
  36.             isTree = false;
  37.             break;
  38.         }
  39.     }
  40.     return isTree;
  41. }
  42.  
  43. int main(){
  44.     ios::sync_with_stdio(false);
  45.     cin >> N;
  46.     mat.resize(N + 2, vector<int>(N + 2, 1));
  47.     paddler.resize(N + 2, vector<int>(N + 2, 0));
  48.  
  49.     vector<con> B;
  50.     vector<con> E;
  51.  
  52.     string in;
  53.  
  54.     for (int i = 1; i <= N; i++){
  55.         cin >> in;
  56.         for (int j = 0; j < in.length(); j++){
  57.             if (in[j] == '1') mat[i][j + 1] = 1;
  58.             else if (in[j] == 'B'){
  59.                 mat[i][j + 1] = 0;
  60.                 B.push_back({i, j + 1, 0, 0});
  61.             }
  62.             else if (in[j] == 'E'){
  63.                 mat[i][j + 1] = 0;
  64.                 E.push_back({i, j + 1, 0, 0});
  65.             }
  66.             else mat[i][j + 1] = 0; 
  67.         }
  68.     }
  69.  
  70.     queue<con> q;
  71.  
  72.     if(E[0].r == E[1].r && E[1].r == E[2].r
  73.     && E[0].c + 1 == E[1].c && E[1].c + 1 == E[2].c) E[1].chk = 0;
  74.     else if(E[0].c == E[1].c && E[1].c == E[2].c
  75.     && E[0].r + 1 == E[1].r && E[1].r + 1 == E[2].r) E[1].chk = 1;
  76.     else {
  77.         printf("0");
  78.         return 0;
  79.     }
  80.  
  81.     if(B[0].r == B[1].r && B[1].r == B[2].r
  82.     && B[0].c + 1 == B[1].c && B[1].c + 1 == B[2].c) q.push(B[1]);
  83.     else if(B[0].c == B[1].c && B[1].c == B[2].c
  84.     && B[0].r + 1 == B[1].r && B[1].r + 1 == B[2].r) {
  85.         B[1].chk = 1;
  86.         q.push({B[1].r, B[1].c, 0, B[1].chk});
  87.     }
  88.     else{
  89.         printf("0");
  90.         return 0;
  91.     }
  92.     visited[B[1].r][B[1].c][B[1].chk] = true;
  93.     paddler[B[1].r][B[1].c] = B[1].chk;
  94.     if (isRotate(B[1].r, B[1].c)){
  95.         q.push({B[1].r, B[1].c, B[1].ct + 1, 1 - B[1].chk});
  96.         visited[B[1].r][B[1].c][1- B[1].chk];
  97.     }
  98.  
  99.     while(q.size()){
  100.         int row = q.front().r;
  101.         int col = q.front().c;
  102.         int cnt = q.front().ct;
  103.         int chk = q.front().chk;
  104.  
  105.         cout << row << " " << col << " " << cnt << " " << chk << endl;
  106.  
  107.         if(row == E[1].r && col == E[1].c && chk == E[1].chk){
  108.             printf("%d", cnt);
  109.             isMove = true;
  110.             break;
  111.         }
  112.  
  113.         for(int i = 0; i < 4; i++){
  114.             int _row = row + ud[i];
  115.             int _col = col + rl[i];
  116.  
  117.             if(mat[_row][_col] == 1) continue;
  118.             else if(chk == 1){
  119.                 if(mat[_row + 1][_col] == 1 || mat[_row - 1][_col] == 1) continue;
  120.                 if(visited[_row][_col][chk]) continue;
  121.                 q.push({_row, _col, cnt + 1, chk});
  122.                 visited[_row][_col][chk] = true;
  123.                 if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
  124.                     q.push({_row, _col, cnt + 2, 1 - chk});
  125.                     visited[_row][_col][1 - chk] = true;
  126.                 }
  127.             }
  128.             else if(chk == 0){
  129.                 if(mat[_row][_col + 1] == 1 || mat[_row][_col - 1] == 1) continue;
  130.                 if(visited[_row][_col][chk]) continue;
  131.                 q.push({_row, _col, cnt + 1, chk});
  132.                 visited[_row][_col][chk] = true;
  133.                 if(isRotate(_row, _col) && !visited[_row][_col][1 - chk]){
  134.                     q.push({_row, _col, cnt + 2, 1 - chk});
  135.                     visited[_row][_col][1 - chk] = true;
  136.                 }
  137.             }
  138.         }
  139.         q.pop();
  140.     }
  141.  
  142.     if(!isMove) cout << 0;
  143.  
  144.     return 0;
  145. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
5
B0011
B0000
B0000
11000
EEE00
stdout
copy 
2 1 0 1
2 2 1 1
2 2 2 0
2 3 2 1
3 2 3 0
1 2 3 0
2 3 3 0
3 3 3 1
3 3 4 0
2 4 4 0
4 3 4 1
3 4 4 1
3 4 5 0
4 4 5 1
4 4 6 0
3 5 5 1
4 5 6 1
5 4 7 0
5 3 8 0
5 2 9 0
9
https://ideone.com/Lc8cig
language:
C++ (gcc 8.3)
created:
5 years 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!