fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <utility>
  4. #include <queue>
  5. #include <tuple>
  6. #define MAX 10
  7. using namespace std;
  8.  
  9. int N, M;
  10. char board[MAX][MAX];
  11. int dy[4] = {-1, 0, 1, 0}; // 위, 오른쪽, 아래, 왼쪽
  12. int dx[4] = {0, 1, 0, -1};
  13. bool visited[MAX][MAX][MAX][MAX];
  14. pair<int, int> p[2]; // index 0 : Red, 1 : Blue
  15.  
  16. int BFS ()
  17. {
  18.     queue<tuple<int, int, int, int>> q;
  19.     q.push(make_tuple(p[0].first, p[0].second, p[1].first, p[1].second));
  20.     visited[p[0].first][p[0].second][p[1].first][p[1].second] = true;
  21.  
  22.     for (int t = 0; t < MAX; t++)
  23.     {
  24.         while (!q.empty())
  25.         {
  26.             int ry = get<0>(q.front());
  27.             int rx = get<1>(q.front());
  28.             int by = get<2>(q.front());
  29.             int bx = get<3>(q.front());
  30.             q.pop();
  31.  
  32.             for (int way = 0; way < 4; way++)
  33.             {
  34.                 bool gameOver[2] = {false, false}; // index 0 : red, 1 : blue
  35.                 int idx = 0; // idx = 1 : red first start, 0 : blue first start
  36.                 int ryy = ry;
  37.                 int rxx = rx;
  38.                 int byy = by;
  39.                 int bxx = bx;
  40.  
  41.                 // dy, dx 순서 : 위, 오른쪽, 아래, 왼쪽
  42.                 // 기울어졌을 때 빨간공, 파란공 중에서 누가 먼저 기울어지는지
  43.                 if ((way == 0 && ryy < byy) || (way == 1 && rxx > bxx) || (way == 2 && ryy > byy) || (way == 3 && rxx < bxx))
  44.                 {
  45.                     idx = 1;
  46.                 }
  47.  
  48.                 for (int i = 0; i < 2; i++)
  49.                 {
  50.                     if (idx == 1)
  51.                     {
  52.                         while (1)
  53.                         {
  54.                             if (board[ryy][rxx] != '.') break;
  55.                             ryy += dy[way];
  56.                             rxx += dx[way];
  57.                         }
  58.  
  59.                         if (board[ryy][rxx] == 'O')
  60.                         {
  61.                             gameOver[0] = true;
  62.                         }
  63.                         else    // 벽에 부딪힘. 전으로 롤백
  64.                         {
  65.                             ryy -= dy[way];
  66.                             rxx -= dx[way];
  67.                             board[ryy][rxx] = 'R';
  68.                         }
  69.  
  70.                         idx = 1 - idx;
  71.                         continue;
  72.                     }
  73.                     else
  74.                     {
  75.                         while (1)
  76.                         {
  77.                             if (board[byy][bxx] != '.') break;
  78.                             byy += dy[way];
  79.                             bxx += dx[way];
  80.                         }
  81.  
  82.                         if (board[byy][bxx] == 'O')
  83.                         {
  84.                             gameOver[1] = true;
  85.                         }
  86.                         else    // 벽에 부딪힘. 전으로 롤백
  87.                         {
  88.                             byy -= dy[way];
  89.                             bxx -= dx[way];
  90.                             board[byy][bxx] = 'B';
  91.                         }
  92.  
  93.                         idx = 1 - idx;
  94.                         continue;
  95.                     }
  96.                 }
  97.  
  98.                 if (gameOver[0] && gameOver[1] == false)
  99.                 {
  100.                     return 1;
  101.                 }
  102.  
  103.                 if (gameOver[0] == false)
  104.                 {
  105.                     board[ryy][rxx] = '.';
  106.                 }
  107.  
  108.                 if (gameOver[1] == false)
  109.                 {
  110.                     board[byy][bxx] = '.';
  111.                 }
  112.  
  113.                 if (gameOver[1] == false)
  114.                 {
  115.                     if (visited[ryy][rxx][byy][bxx])    continue;
  116.  
  117.                     visited[ryy][rxx][byy][bxx] = true;
  118.                     q.push(make_tuple(ryy, rxx, byy, bxx));
  119.                 }
  120.             }
  121.         }
  122.     }
  123.  
  124.     return 0;
  125. }
  126.  
  127. int main()
  128. {
  129.     ios_base::sync_with_stdio(0);
  130.     cin.tie(0);
  131.     cout.tie(0);
  132.  
  133.     cin >> N >> M;
  134.     for (int i = 0; i < N; i++)
  135.     {
  136.         string s;
  137.         cin >> s;
  138.         for (int j = 0; j < s.size(); j++)
  139.         {
  140.             if (s[j] == 'R')
  141.             {
  142.                 p[0] = make_pair(i, j);
  143.                 board[i][j] = '.';
  144.             }
  145.  
  146.             else if (s[j] == 'B')
  147.             {
  148.                 p[1] = make_pair(i, j);
  149.                 board[i][j] = '.';
  150.             }
  151.  
  152.             else
  153.                 board[i][j] = s[j];
  154.         }
  155.     }
  156.  
  157.     cout << BFS() << '\n';
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
6 6
######
#...R#
###..#
#.OB##
##...#
######
stdout
copy 
1
https://ideone.com/WYQ5Iy
language:
C++14 (gcc 8.3)
created:
1 year 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!