P1363 【幻想迷宫】

ygsldr · 2017-08-25 21:02:23 · 题解

咳，这题卡了很久，很大原因是思路走错(看不懂题解)

具体思路：放大放大再放大，然后走到边界就传送

很明显，假如能走到之前走到过的环境相同的点（即(x mod n,y mod m)），记作A->B，那么就一定有B->同一个环境（(x mod n,y mod m)）的点

//同一个环境就是他的映射位置相同

细节见下面：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MEM(arr,num) memset(arr,num,sizeof(arr))
#define FOR(i,l,r) for(int i(l);i < r;++i)
#define SIZE 1511
using namespace std;

char board[SIZE][SIZE];
bool map1[SIZE * 2][SIZE * 2], map2[SIZE][SIZE];
//map1表示有无走到过这个点，map2表示有无走到过映射点
int n, m, dn, dm;

bool dfs(int x,int y)
{
    if(x == -1)
    {
        if(dfs(dn - 1, y))return true;
        return false;
    }
    if(x == dn)
    {
        if(dfs(0, y))return true;
        return false;
    }
    if(y == -1)
    {
        if(dfs(x, dm - 1))return true;
        return false;
    }
    if(y == dm)
    {
        if(dfs(x, 0))return true;
        return false;
    }//上面四个if表示是否到边界，是就传送
    if(map1[x][y] || board[x % n][y % m] == '#')
    {
        return false;
    }//判断能不能走
    if(map2[x % n][y % m])
    {
        return true;
    }//判断这有没有走到这个点的映射
    map1[x][y] = true;
    map2[x % n][y % m] = true;
    //记录
    if(dfs(x + 1, y))return true;
    if(dfs(x - 1, y))return true;
    if(dfs(x, y + 1))return true;
    if(dfs(x, y - 1))return true;
    //遍历
    return false;
}

int main()
{
    while(cin >> n >> m)
    {
        dn = n * 2;
        dm = m * 2;
        int sx, sy;
        FOR(i, 0, n)
        {
            FOR(j, 0, m)
            {
                cin >> board[i][j];
                if(board[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
            }
        }//输入+找起点
        MEM(map1, 0);
        MEM(map2, 0);
        if(dfs(sx, sy))    printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}