问题描述

给定一个R行C列的地图，地图的每一个方格可能是’#’, ‘+’, ‘-‘, ‘|’, ‘.’, ‘S’, ‘T’七个字符中的一个，分别表示如下意思：
‘#’: 任何时候玩家都不能移动到此方格；
‘+’: 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格；
‘-‘: 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非’#’方格移动一格；
‘|’: 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非’#’方格移动一格；
‘.’: 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为’#’，则玩家不能再移动；
‘S’: 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格；
‘T’: 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1.玩家可以从初始位置移动到此方格；
2.玩家不可以从此方格移动到目标位置。

输入格式

输入的第一行包括两个整数R 和C，分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。
接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个’S’和一个’T’。

输出格式

如果玩家在初始位置就已经不能到达终点了，就输出“I’m stuck!”（不含双引号）。否则的话，输出满足性质的方格的个数。

样例输入

5 5
–+-+
..|#.
..|##
S-+-T
####.

样例输出

2

样例说明

如果把满足性质的方格在地图上用’X’标记出来的话，地图如下所示：
–+-+
..|#X
..|##
S-+-T
####X

解题思路：

从S出发找到所有能到的点，从T出发，逆着过程找到所有能到T的点。

关键：如何从T开始逆着过程找能到T的点。

如果当前点的某一方向有点x，那么该x必须要满足能走到当前点，才能继续从x为起点搜索下去。
如当前点的上方有一点，那么上方的点必须要有往下走能力才能算从上方的点能走到T。

tips:

1.在深搜过程不主动return，最后会根据限制条件走遍所有能走的点；
2.vis数组直接用来保存能到的点，在回溯时不用置0。因为只要考虑能否走到某一点；
3.如果不逆过程，而是对每一个点都进行一遍搜索看能否到T，会超出时间限制。

参考代码

#include<iostream>
#include<string.h>
using namespace std;
int r = 0,c = 0;
int dir[4][2] = {{0,-1}, {0, 1}, {-1,0}, {1, 0}};//左 右 上 下 
int flag = 0;
char map[55][55];
bool visS[55][55],visT[55][55];//visS用于记录s点出发能到的所有点 ，visT用于记录能到T的点 
int inbod(int x, int y)
{
    return x < r && x >= 0 && y < c && y >=0;
 } 
void dfsS(int x,int y)
{    
    visS[x][y] = 1;
    if(map[x][y] == 'T') {//找到T 
        flag = 1;
    }
    //按方向划分 左右上下
    if (map[x][y] == 'S' || map[x][y] == '-' || map[x][y] == '+' || map[x][y] == 'T') {
        if (inbod(x, y - 1) && !visS[x][y - 1] && map[x][y - 1] != '#') {
            dfsS(x, y - 1);
        }
    }
    if (map[x][y] == 'S' || map[x][y] == '-' || map[x][y] == '+' || map[x][y] == 'T') {
        if (inbod(x, y + 1) && !visS[x][y + 1] && map[x][y + 1] != '#') {
            dfsS(x, y + 1);
        }
    }
    if (map[x][y] == 'S' || map[x][y] == '+' || map[x][y] == 'T' ||  map[x][y] == '|') {
        if (inbod(x - 1, y) && !visS[x - 1][y] && map[x - 1][y] != '#') {
            dfsS(x - 1, y);
        }
    }
    if (map[x][y] == 'S' || map[x][y] == '.' || map[x][y] == '+' || map[x][y] == 'T' || map[x][y] == '|') {
        if (inbod(x + 1, y) && !visS[x + 1][y] && map[x + 1][y] != '#') {
            dfsS(x + 1, y);
        }
    }

 } 
void dfsT(int x,int y)
{    

    visT[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int tx, ty;
        tx = x + dir[i][0];
        ty = y + dir[i][1]; 

        if(inbod(tx, ty) && map[tx][ty] != '#') {
            if(i == 0 && (map[tx][ty] == 'S' || map[tx][ty] == '-' || map[tx][ty] == '+' || map[tx][ty] == 'T') && visT[tx][ty] == 0) dfsT(tx, ty);//在当前点左边的点，该点必须要有往右的能力 
            if(i == 1 && (map[tx][ty] == 'S' || map[tx][ty] == '-' || map[tx][ty] == '+' || map[tx][ty] == 'T' ) && visT[tx][ty] == 0) dfsT(tx, ty);
            if(i == 2 && (map[tx][ty] == 'S' || map[tx][ty] == '.' || map[tx][ty] == '+' || map[tx][ty] == 'T' || map[tx][ty] == '|') && visT[tx][ty] == 0) dfsT(tx, ty);
            if(i == 3 && (map[tx][ty] == 'S' || map[tx][ty] == '+' || map[tx][ty] == 'T' || map[tx][ty] == '|') && visT[tx][ty] == 0) dfsT(tx, ty);//在当前点下面，该点必须要有往上的能力 
        }

     } 



 } 
int main()
{
    int sx = 0,sy = 0, ex = 0, ey = 0;
    cin >> r >> c;
    for (int i= 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
            if(map[i][j] == 'S') {
                sx = i;
                sy = j;
            }
            if(map[i][j] == 'T') {
                ex = i;
                ey = j;
            }
        }
    }
    dfsS(sx, sy);
    if (flag == 0) {//能否找到T
        cout << "I'm stuck!";
        return 0; 
    }
    dfsT(ex, ey);//从T开始，逆找能到T的点 
    int cnt = 0;
    for (int i= 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (visS[i][j] == 1 && visT[i][j] == 0) {//S能到，且不能到T 
                cnt ++;
            }
        }
    }
    cout << cnt;
    return 0;
}