秋招准备-网易秋招笔试-9

地牢逃脱：

给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x₀ , y₀) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x₀, y₀，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）

输出描述:

输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。

示例1

输入

3 3
...
...
...
0 1
4
1 0
0 1
-1 0
0 -1

输出

3

思路：
这题描述真实考验语文水平···其实就是输入迷宫，找到所有最短到达所有不是墙的点的路线，输出这些路线中最长的那个，如果有根本不可能到达的点，直接输出-1.
所以实际上就是把所有点都当作终点跑一遍bfs找最短路线。

#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
struct Node//每个节点
{
    int x;//节点位置
    int y;
    bool isX;//是否是墙
    bool walked;//是否走过
    int cengshu;//bfs搜索中处于的层数
};

int main() {
//开始输入
    int n,m;
    cin >> n>>m;
    
    vector<vector<Node>> ss;
    int sX, sY;
    
    for (int i = 0; i < n; i++) {
        vector<Node> t;
        string aa;
        cin >> aa;
        for (int j = 0; j < m; j++) {
            
            Node node{ i, j, aa[j] == 'X' , false, 0 };
            t.push_back(node);
        }
        ss.push_back(t);
    }
    cin >> sX >> sY;
    int k;
    cin >> k;
    vector<vector<int>> bu;
    for (int i = 0; i < k; i++) {
        vector<int> tt;
        int xx, yy;
        cin >> xx >> yy;
        tt.push_back(xx);
        tt.push_back(yy);
        bu.push_back(tt);
    }
//输入完毕

    vector<int> fin;
    for (int i = 0; i < n; i++) {//对于每个不是墙的节点进行遍历
        for (int j = 0; j < m; j++) {   
            //复制一个ss迷宫进行bfs因为要进行不止一次bfs。
            vector<vector<Node>> s = ss;
            if (!s[i][j].isX && !(i == sX && j == sY)) {
                //如果节点不是起点且不是墙，开始以该点为终点进行bfs搜索
                //终点就是（i，j）
                bool can = false;//后续跳出循环的判断
                queue<Node*> q;//bfs队列
                Node *vt;//指向队列弹出的节点
                Node *vf;//指向vt能走的下一个节点
                q.push(&s[sX][sY]);//把第一个节点推进去
                s[sX][sY].walked = true;//设置已经走过
                while (!q.empty()) {//队列为空说明无法到达该点，此时can没有改过因此仍为false
                    vt = q.front();
                    q.pop();

                    for (int iii = 0; iii < k; iii++) {
                        int dx = bu[iii][0];
                        int dy = bu[iii][1];
                        if ((vt->x + dx) >= 0 && (vt->x + dx) < n&& (vt->y + dy) >= 0 && (vt->y + dy) < m) {
                            //确定能以步长移动不越界
                            vf = &s[vt->x + dx][vt->y + dy];
                            if (!vf->isX) {//不是墙才开始判断
                                if (vt->x + dx == i && vt->y + dy == j) {//如果为终点
                                    fin.push_back(vt->cengshu + 1);//推送发到达此点的层数
                                    can = true;//这时修改为true，使得下一步跳出时不会触发输出-1.
                                    break;//强退当前bfs，搜索下一节点。                 
                                }
                                if (!vf->walked) {
                                    q.push(vf);
                                    vf->walked = true;
                                    vf->cengshu = vt->cengshu + 1;
                                }
                            }
                            
                            
                        }
                    }
                    if (can)break;//强退while循环
                }
                if (!can) {//can为false说明该循环是自然完成，说明有点无法到达，直接输出-1
                    cout << -1 << endl;
                    return 0;
                }
                
            }
        }
    }

    int maxf = 0;
    for (int i = 0; i < fin.size(); i++) {
        maxf = max(maxf, fin[i]);//输出最大的那条路的层数
    }

    cout << maxf << endl;


    return 0;

}