CCF I’m stuck!

梦里梦外; 2021-09-14 03:26 220阅读 0赞

## **一、试题** ##

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

#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;
    }

[Link 1]: http://blog.csdn.net/qiangli_strong/article/details/51144586