洛谷 幻想迷宫

题号:1363
首先放上来一个AC代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
char map[1505][1505];
int visited[1505][1505][2];
bool dfs(int orix, int oriy){
    int x = (orix%n+n) % n, y = (oriy%m+m) % m;
    if (map[x][y] != 'S' && map[x][y] != '.')return false;
    if (orix== visited[x][y][0]&&oriy==visited[x][y][1])return false;
    if (visited[x][y][0] != -1)return true;
    visited[x][y][0] = orix;
    visited[x][y][1] = oriy;
    if (dfs(orix + 1, oriy))return true;
    if (dfs(orix - 1, oriy))return true;
    if (dfs(orix, oriy + 1))return true;
    if (dfs(orix, oriy - 1))return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin >> n >> m){
        memset(visited, -1, sizeof(visited));
        for (int i = 0; i < n; i++)cin >> map[i];
        int sx, sy;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == 'S'){
                    sx = i;
                    sy = j;
                    break;
                }
            }
        }
        bool flag = dfs(sx, sy);
        if (flag)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

题解页面:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1363
该思路参考:作者: mike_he 更新时间: 2016-07-27 20:57
有两种思路是错误的,在下面列举一下:

1、是想着把x/y压缩一下,代码如下,注意与AC代码的不同点:(70分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
char map[1505][1505];
int visited[1505][1505];
bool dfs(int orix, int oriy){
    int x = (orix%n+n) % n, y = (oriy%m+m) % m;
    if (map[x][y] != 'S' && map[x][y] != '.')return false;
    if (orix + oriy == visited[x][y])return false;
    if (visited[x][y] != -1)return true;
    visited[x][y] = orix+oriy;
    if (dfs(orix + 1, oriy))return true;
    if (dfs(orix - 1, oriy))return true;
    if (dfs(orix, oriy + 1))return true;
    if (dfs(orix, oriy - 1))return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin >> n >> m){
        memset(visited, -1, sizeof(visited));
        for (int i = 0; i < n; i++)cin >> map[i];
        int sx, sy;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == 'S'){
                    sx = i;
                    sy = j;
                    break;
                }
            }
        }
        bool flag = dfs(sx, sy);
        if (flag)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

2、DFS的取模问题,这个我也搞不太懂,看上面的题解里说了,但是也没看懂……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
char map[1505][1505];
int visited[1505][1505][2];
bool dfs(int orix, int oriy){
    int x = (orix+n) % n, y = (oriy+m) % m;  //这里
    if (map[x][y] != 'S' && map[x][y] != '.')return false;
    if (orix== visited[x][y][0]&&oriy==visited[x][y][1])return false;
    if (visited[x][y][0] != -1)return true;
    visited[x][y][0] = orix;
    visited[x][y][1] = oriy;
    if (dfs(orix + 1, oriy))return true;
    if (dfs(orix - 1, oriy))return true;
    if (dfs(orix, oriy + 1))return true;
    if (dfs(orix, oriy - 1))return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin >> n >> m){
        memset(visited, -1, sizeof(visited));
        for (int i = 0; i < n; i++)cin >> map[i];
        int sx, sy;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == 'S'){
                    sx = i;
                    sy = j;
                    break;
                }
            }
        }
        bool flag = dfs(sx, sy);
        if (flag)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

就这两个地方需要注意。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注