CCF I’m stuck!-蒲公英云

一、试题

问题描述
　　给定一个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点深搜，比较取值。需要注意两种搜法区别。
代码来源

#include <iostream>
#include <memory.h>
using namespace std;
#define DIM 50
int R,C;
char G[DIM][DIM];
bool sCanReach[DIM][DIM];//起点能到达的矩阵
bool tCanReach[DIM][DIM];//终点能到的矩阵
//正向深搜，从起点出发
void ForwardDFS(bool sign[DIM][DIM], int curR, int curC){
    int Row = R, Col = C;
    //若 当前点已走过 或 当前点是障碍物，停止递归
    if (sign[curR][curC] || G[curR][curC] == '#')
    {
        return ;
    }
    //标记此点可达
    sign[curR][curC] = true;
    //标记可以往哪个方向移动
    bool up,down,left,right;
    up = down = left = right = false;
    if (G[curR][curC] == '.')//向下移动
    {
        down = true;
    }else if (G[curR][curC] == '-')//左右移动
    {
        left = right = true;
    }else if (G[curR][curC] == '|')//上下移动
    {
        up = down = true;
    }else if (G[curR][curC] == '+' || G[curR][curC] == 'S' || G[curR][curC] == 'T')//上下左右移动
    {
        up = down = left = right = true;
    }
    //上
    if (up && curR-1 >= 0)
    {
        ForwardDFS(sign,curR-1,curC);
    }
    //下
    if (down && curR+1 < Row)
    {
        ForwardDFS(sign,curR+1,curC);
    }
    //左
    if (left && curC-1 >= 0)
    {
        ForwardDFS(sign,curR,curC-1);
    }
    //右
    if (right && curC+1 < Col)
    {
        ForwardDFS(sign,curR,curC+1);
    }
}
//从终点出发，反向DFS
// 反向搜索的方法不能跟之前正向一样，假设T上面一个-，按照正向那么是可以走通的，但是对于反向来说，从-显然不能走到下方的T。
// 所以反向是从上一点试探性的向上下左右走一步到达下一点，然后以下一点为基准判断是否能走到上一点。
void ReserveDFS(bool sign[DIM][DIM],int curR, int curC,/*当前点 */int preR, int preC /*上一个点*/)
{
    int Row = R, Col = C;
    //若 当前点已走过 或 当前点是障碍物，停止递归
    if (sign[curR][curC] || G[curR][curC] == '#')
    {
        return ;
    }
    //从下面来的，可以返回去，其他方向来的无法原路返回
    if (G[curR][curC] == '.' && preR == curR+1 && preC == curC)
    {
        sign[curR][curC] = true;
    }else if (G[curR][curC] == '-' && preR == curR)
    {
        sign[curR][curC] = true;
    }else if (G[curR][curC] == '|' && preC == curC)
    {
        sign[curR][curC] = true;
    }else if (G[curR][curC] == 'S' || G[curR][curC] == '+' || G[curR][curC] == 'T')
    {
        sign[curR][curC] = true;
    }
    //没有方式可以从下一点走到上一点，那么无需再试探，直接返回
    if (sign[curR][curC] == false)
    {
        return ;
    }
    //上
    if (curR-1 >= 0)
    {
        ReserveDFS(sign,curR-1,curC,curR,curC);
    }
    //下
    if (curR+1 < Row)
    {
        ReserveDFS(sign,curR+1,curC,curR,curC);
    }
    //左
    if (curC-1 >= 0)
    {
        ReserveDFS(sign,curR,curC-1,curR,curC);
    }
    //右
    if (curC+1 < Col)
    {
        ReserveDFS(sign,curR,curC+1,curR,curC);
    }
}
int main()
{
    memset(sCanReach, 0, sizeof(sCanReach));
    memset(tCanReach, 0, sizeof(tCanReach));
    cin>>R>>C;
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            cin>>G[i][j];
        }
    }
    //处理
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            if (G[i][j] == 'S')
            {
                ForwardDFS(sCanReach,i,j);
            }
        }
    }
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            if (G[i][j] == 'T')
            {
                // 如果起点到终点都没有那么直接输出
                if (sCanReach[i][j] == false)
                {
                    cout<<"I'm stuck!"<<endl;
                    return 0;
                }
                ReserveDFS(tCanReach,i,j,i,j);
            }
        }
    }
    int num = 0;
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            // 注意除去自身
            if (G[i][j] != 'S' && G[i][j] != 'T' &&
                sCanReach[i][j]  && !tCanReach[i][j])
            {
                num++;
            }
        }
    }
    cout<<num<<endl;
    return 0;
}