题号：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; } } |
就这两个地方需要注意。。