3046: 【普及+/提高】【P1363】幻象迷宫

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：8 解决：4

题目描述

幻象迷宫可以认为是无限大的，不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路，用'.'表示；有的地方是墙，用'#'表示。LHX和WD所在的位置用'S'表示。也就是对于迷宫中的一个点(x,y)，如果(x mod n,y mod m)是'.'或者'S'，那么这个地方是道路；如果(x mod n,y mod m)是'#'，那么这个地方是墙。LHX和WD可以向上下左右四个方向移动，当然不能移动到墙上。

请你告诉LHX和WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。。。

输入

输入包含多组数据，以EOF结尾。

每组数据的第一行是两个整数N、M。

接下来是一个N*M的字符矩阵，表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。

输出

对于每组数据，输出一个字符串，Yes或者No。

样例输入 复制 

5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##

样例输出 复制 

Yes
No

提示

对于30%的数据，N,M<=20

对于50%的数据，N.M<=100.

对于100%的数据，N,M<=1500，每个测试点不超过10组数据.

BFS: 


#include<bits/stdc++.h>
using namespace std;
const int N = 1510;
struct coord {
    int x;
    int y;
};
//路径中的某个点，如果再次被访问到，并且，不是原来的前驱时，就可以交替进行这样的操作，不断外延出去。
//走迷宫下右上左
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m;
int sx, sy;//出发点坐标
char g[N][N];       //地图
int book[N][N][3];  // book[ u ][v][0]:是否访问过，book[ u ][v][1]:x，book[ u ][v][2]:y
/**
 * 功能：正数+负数取模
 */
int MOD(int a, int b) {
    return (a % b + b) % b;
}
//广度优先搜索
bool bfs() {
    queue<coord> q;           //声明队列
    q.push({sx, sy});       //将出发点放入队列
    //标识起点已使用，并且第一次到达时，真实坐标是x,y
    book[sx][sy][0] = 1, book[sx][sy][1] = sx, book[sx][sy][2] = sy;
    //开始套路
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            //因为可能出现负数，使用负数取模运算
            int u = MOD(tx, n), v = MOD(ty, m);
            //如果不是墙
            if (g[ u ][v] != '#') {
                //如果走过.而且与上次过来的位置不一样的话，就是肯定能走出去
                if (!book[ u ][v][0]) {
                    //没有走过，入队列
                    q.push({tx, ty});
                    //标识已使用，并且第一次到达的坐标是a,b
                    book[ u ][v][0] = 1, book[ u ][v][1] = tx, book[ u ][v][2] = ty;
                } else if ((book[ u ][ v ][1] != tx || book[ u ][v][2] != ty)) return true;
            }
        }
    }
    return false;
}
int main() {
    while (cin >> n >> m) {
        //每次清空,地图数组不用每次清空，因为每次都全新读入，自
        memset(book, 0, sizeof book);
        //双重循环读入地图
        // 注意i是从0开始，到n-1结束,这是因为：表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。
        // 注意j是从0开始，到m-1结束,这是因为：表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> g[i][j];
                if (g[i][j] == 'S')sx = i, sy = j;     //标识起点
            }
        //广度优先
        if (bfs())cout << "Yes" << endl;    //可以走出幻象迷宫
        else cout << "No" << endl;            //不能走出幻象迷宫
    }
}


来源/分类

提交提交记录统计露一手!