fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dx[5] = { 0, 0, 1, 0, -1 };
  5. int dy[5] = { 0, -1, 0, 1, 0 };
  6.  
  7. typedef pair<int,int> pii;
  8. typedef pair<pii,pii> state;
  9.  
  10. state st( int x1, int y1, int x2, int y2 )
  11. {
  12.     return make_pair( make_pair(x1, y1), make_pair(x2, y2) );
  13. }
  14.  
  15. bool check( int x, int y, int n, int m )
  16. {
  17.     return x >= 0 && y >= 0 && x < n && y < m;
  18. }
  19.  
  20. int main()
  21. {
  22.     int n, m;
  23.  
  24.     while (scanf("%d %d\n", &n, &m) == 2)
  25.     {
  26.         if (!n && !m) break;
  27.  
  28.         char a[n][m] = { 0 };
  29.         for (int i = 0; i < n; i++)
  30.             scanf("%s", a[i]);
  31.         int xa = -1, ya = -1;
  32.         int xb = -1, yb = -1;
  33.         for (int i = 0; i < n; i++)
  34.             for (int j = 0; j < m; j++)
  35.             {
  36.                 if (a[i][j] == 'a') xa = i, ya = j;
  37.                 if (a[i][j] == 'b') xb = i, yb = j;
  38.             }
  39.  
  40.         queue<state> q;
  41.         q.push(st(xa, ya, xb, yb));
  42.         int d[n][m][n][m] = { 0 };
  43.         char u[n][m][n][m] = { 0 };
  44.  
  45.         while (!q.empty())
  46.         {
  47.             state s = q.front(); q.pop();
  48.             int x1 = s.first.first;
  49.             int y1 = s.first.second;
  50.             int x2 = s.second.first;
  51.             int y2 = s.second.second;
  52.  
  53.             for (int i = 0; i < 5; i++)
  54.             {
  55.                 int xx1 = x1 + dx[i], yy1 = y1 + dy[i];
  56.                 if (check(xx1, yy1, n, m) && a[xx1][yy1] != '#')
  57.                     for (int j = 0; j < 5; j++)
  58.                     {
  59.                         int xx2 = x2 + dx[j], yy2 = y2 + dy[j];
  60.                         if (check(xx2, yy2, n, m) && a[xx2][yy2] != '#' && !u[xx1][yy1][xx2][yy2])
  61.                             if (!(xx1 == x2 && yy1 == y2) && !(xx2 == x1 && yy2 == y1) && !(xx1 == xx2 && yy1 == yy2))
  62.                             {
  63.                                 q.push(st(xx1, yy1, xx2, yy2));
  64.                                 u[xx1][yy1][xx2][yy2] = 1;
  65.                                 d[xx1][yy1][xx2][yy2] = d[x1][y1][x2][y2] + 1;
  66.                             }
  67.                     }
  68.             }
  69.         }
  70.  
  71.         if (u[xb][yb][xa][ya])
  72.             printf("%d\n", d[xb][yb][xa][ya]);
  73.         else
  74.             puts("IMPOSSIBLE");
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 4
#..#
a..b
####
3 7
#######
#a...b#
#######
4 4
a...
###.
##..
b...
0 0
stdout
copy 
6
IMPOSSIBLE
15
https://ideone.com/b9m0io
language:
C++ (gcc 8.3)
created:
5 years 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!