1 /************************************************************** 2     Problem: 3393 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:36 ms 7     Memory:1156 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 #include <queue>14  15 using namespace std;16 const int dx[4] = {0, 1, 0, -1};17 const int dy[4] = {1, 0, -1, 0};18 const int N = 105;19 const int inf = (int) 1e9;20  21 struct data {22     int x, y, to, dis;23     data() {}24     data(int _x, int _y, int _t, int _d) : x(_x), y(_y), to(_t), dis(_d) {}25      26     inline bool operator < (const data &b) const {27         return dis > b.dis;28     }29 };30  31 int n, m, ans;32 int sx, sy, ex, ey;33 int dis[N][N][4], w[N][N];34 priority_queue <data> q;35  36 inline bool in(int x, int y) {37     return 1 <= x && x <= n && 1 <= y && y <= m;38 }39  40 int main() {41     int i, j;42     char ch;43     scanf("%d%d", &m, &n);44     for (i = 1; i <= n; ++i)45         for (j = 1; j <= m; ++j) {46         ch = getchar();47         while (ch != ‘C‘ && ch != ‘.‘ && ch != ‘*‘)48             ch = getchar();49         if (ch == ‘*‘) w[i][j] = 1;50         if (ch == ‘C‘)51             if (!sx) sx = i, sy = j;52             else ex = i, ey = j;53     }54     memset(dis, 127 / 3, sizeof(dis));55     for (i = 0; i < 4; ++i) {56         q.push(data(sx, sy, i, 0));57         dis[sx][sy][i] = 0;58     }59      60     int x, y, k, x1, y1;61     while (!q.empty()) {62         x1 = x = q.top().x, y1 = y = q.top().y, k = q.top().to;63         while (in(x1 += dx[k], y1 += dy[k]) && !w[x1][y1] && dis[x1][y1][k] > dis[x][y][k]) {64             dis[x1][y1][k] = dis[x][y][k];65             q.push(data(x1, y1, k, dis[x][y][k]));66         }67         for (i = 0; i < 4; ++i)68             if (dis[x][y][i] > q.top().dis + 1) {69                 dis[x][y][i] = q.top().dis + 1;70                 q.push(data(x, y, i, dis[x][y][i]));71             }72         q.pop();73     }74     for (i = 0, ans = inf; i < 4; ++i)75         ans = min(ans, dis[ex][ey][i]);76     printf("%d\n", ans);77     return 0;78 }