fork(1) 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.                     if (idx == 0)
  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.                 	cout << '\n';
  101.                 	for (int n = 0; n < N; n++)
  102.                 	{
  103.                 		for (int m = 0; m < M; m++)
  104.                 		{
  105.                 			cout << board[n][m] << ' ';
  106.                 		}
  107.                 		cout << '\n';
  108.                 	}
  109.                     return 1;
  110.                 }
  111.  
  112.                 if (gameOver[0] == false)
  113.                 {
  114.                     board[ryy][rxx] = '.';
  115.                 }
  116.  
  117.                 if (gameOver[1] == false)
  118.                 {
  119.                     board[byy][bxx] = '.';
  120.                 }
  121.  
  122.                 if (gameOver[1] == false)
  123.                 {
  124.                     if (visited[ryy][rxx][byy][bxx])    continue;
  125.  
  126.                     visited[ryy][rxx][byy][bxx] = true;
  127.                     q.push(make_tuple(ryy, rxx, byy, bxx));
  128.                 }
  129.             }
  130.         }
  131.     }
  132.  
  133.     return 0;
  134. }
  135.  
  136. int main()
  137. {
  138.     ios_base::sync_with_stdio(0);
  139.     cin.tie(0);
  140.     cout.tie(0);
  141.  
  142.     cin >> N >> M;
  143.     for (int i = 0; i < N; i++)
  144.     {
  145.         string s;
  146.         cin >> s;
  147.         for (int j = 0; j < s.size(); j++)
  148.         {
  149.             if (s[j] == 'R')
  150.             {
  151.                 p[0] = make_pair(i, j);
  152.                 board[i][j] = '.';
  153.             }
  154.  
  155.             else if (s[j] == 'B')
  156.             {
  157.                 p[1] = make_pair(i, j);
  158.                 board[i][j] = '.';
  159.             }
  160.  
  161.             else
  162.                 board[i][j] = s[j];
  163.         }
  164.     }
  165.  
  166.     cout << BFS() << '\n';
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########
stdout
copy 
0
https://ideone.com/0u6Kaj
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!