1432.输油管道

Time Limits: 1000 ms Memory Limits: 65536 KB

Description

请你帮忙设计一个从城市M到城市Z的输油管道，现在已经把整个区域划分为R行C列，每个单元格可能是空的也可能是以下7种基本管道之一：
　　

油从城市M流向Z，‘+’型管道比较特殊，因为石油必须在两个方向（垂直和水平）上传输，如下图所示：


现在恐怖分子弄到了输油管道的设计图，并把其中一个单元格中的管道偷走了，请你帮忙找到偷走的管道的位置以及形状。

Input

第一行包含两个整数R和C（1<=R,C<=25）。
　　接下来R行每行C个字符描述被偷之后的形状，字符分为以下三种：
　　(1)‘.’表示空；
　　(2)字符‘|’（ASCII为124）、‘-’、‘+’、‘1’、‘2’、‘3’、‘4’描述管道的形状；
　　(3)‘M’和‘Z’表示城市，两个都是只出现一次。
　　输入保证石油的流向是唯一的，只有一个管道跟M和Z相连，除此此外，保证没有多余的管道，也就是说所有的管道在加进被偷的管道后一定都会被用上。
　　输入保证有解而且是唯一的。

Output

输出被偷走的管道的行号和列号以及管道的类型。

Sample Input

输入1：
3 7
.......
.M-.-Z.
.......

输入2：
3 5
..1-M
1-+..
Z.23.

输入3：
6 10
Z.1----4..
|.|....|..
|..14..M..
2-+++4....
..2323....
..........

Sample Output

输出1：
2 4 -

输出2：
2 4 4

输出3：
3 3 |

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXRC = 25+5;
const int cmpdis[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };
const int cmppipe[5][2] = { {0, 0}, {1, 2}, {3, 2}, {3, 0}, {1, 0} };

char g[MAXRC][MAXRC];

int r, c, sx, sy, fx, fy;

inline bool SF (int x, int y) {
    return (x == fx && y == fy || x == sx && y == sy);
}

inline void check (int x, int y, int dis) {
    int i=dis;
    if ((g[x+1][y] == '|' || SF(x+1, y) || g[x+1][y] == '2' || g[x+1][y] == '3' || g[x+1][y] == '+') && (g[x-1][y] == '|' || SF(x-1, y) || g[x-1][y] == '1' || g[x-1][y] == '4' || g[x-1][y] == '+') && (g[x][y-1] == '-' || SF(x, y-1) || g[x][y-1] == '1' || g[x][y-1] == '2' || g[x][y-1] == '+') && (g[x][y+1] == '-' || SF(x, y+1) || g[x][y+1] == '4' || g[x][y+1] == '3' || g[x][y+1] == '+')) {
        printf ("%d %d +\n", x, y);
        exit (0);
    }
    if ((dis == 0)) {
        int nx=x + cmpdis[i][0];
        int ny=y + cmpdis[i][1];
        if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '2' || SF (nx, ny)){
            printf ("%d %d -\n", x, y);
            exit(0);
        }
    }
    if ((dis == 2)) {
        int nx=x + cmpdis[i][0];
        int ny=y + cmpdis[i][1];
        if (g[nx][ny] == '-' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '4' || SF (nx, ny)){
            printf ("%d %d -\n", x, y);
            exit(0);
        }
    }
    if ((dis == 1)) {
        int nx=x + cmpdis[i][0];
        int ny=y + cmpdis[i][1];
        if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '3' || g[nx][ny] == '2' || SF (nx, ny)){
            printf ("%d %d |\n", x, y);
            exit(0);
        }
    }
    if ((dis == 3)) {
        int nx=x + cmpdis[i][0];
        int ny=y + cmpdis[i][1];
        if (g[nx][ny] == '|' || g[nx][ny] == '+' || g[nx][ny] == '1' || g[nx][ny] == '4' || SF (nx, ny)){
            printf ("%d %d |\n", x, y);
            exit(0);
        }
    }
    if (dis == 3) {
        if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
            printf ("%d %d 1\n", x, y);
            exit(0);
        }
    }
    if (dis == 0) {
        if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
            printf ("%d %d 1\n", x, y);
            exit(0);
        }
    }
    if (dis == 1) {
        if (g[x][y+1] == '-' || g[x][y+1] == '+' || g[x][y+1] == '3' || g[x][y+1] == '4' || SF (x, y+1)) {
            printf ("%d %d 2\n", x, y);
            exit(0);
        }
    }
    if (dis == 0) {
        if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
            printf ("%d %d 2\n", x, y);
            exit(0);
        }
    }
    if (dis == 2) {
        if (g[x-1][y] == '|' || g[x-1][y] == '+' || g[x-1][y] == '1' || g[x-1][y] == '4' || SF (x-1, y)) {
            printf ("%d %d 3\n", x, y);
            exit(0);
        }
    }
    if (dis == 1) {
        if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
            printf ("%d %d 3\n", x, y);
            exit(0);
        }
    }
    if (dis == 2) {
        if (g[x+1][y] == '|' || g[x+1][y] == '+' || g[x+1][y] == '2' || g[x+1][y] == '3' || SF (x+1, y)) {
            printf ("%d %d 4\n", x, y);
            exit(0);
        }
    }
    if (dis == 3) {
        if (g[x][y-1] == '-' || g[x][y-1] == '+' || g[x][y-1] == '1' || g[x][y-1] == '2' || SF (x, y-1)) {
            printf ("%d %d 4\n", x, y);
            exit(0);
        }
    }
    return;
}
        
void dfs (int x, int y, int dis) {
    if (dis == -1) {
        for (int i=0; i<4; i++) {
            int nx=x + cmpdis[i][0];
            int ny=y + cmpdis[i][1];
            if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
            if (g[nx][ny] == '.') {
                check(nx, ny, i);
                continue;
            }
            if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
                dfs (nx, ny, cmppipe[g[nx][ny] - '0'][i%2]);
                return;
            }
            else {
                dfs (nx, ny, i);
                return;
            }
        }
    }
    int nx=x + cmpdis[dis][0];
    int ny=y + cmpdis[dis][1];
    if (g[nx][ny] == '.') {
        check(nx, ny, dis);
    }
    if (1 <= g[nx][ny] - '0' && g[nx][ny] - '0' <=4) {
        dfs (nx, ny, cmppipe[g[nx][ny] - '0'][dis%2]);
        return;
    }
    else {
        dfs (nx, ny, dis);
        return;
    }
    return;
}

int main() {
    cin>>r>>c;
    for (int i=1; i<=r; i++) {
        for (int j=1; j<=c; j++) {
            char ch;
            cin >>ch;
            g[i][j]=ch;
            if (g[i][j] == 'M') {
                sx=i;
                sy=j;
            }
            if (g[i][j] == 'Z') {
                fx=i;
                fy=j;
            }
        }
    }
    dfs (sx,sy,-1);
    return 0;
}