[successbox title="P1238 走迷宫"]题目描述

有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。

https://www.luogu.org/problem/show?pid=1238

[/successbox]

题解：
水水的DFS...注意记录和搜索方向就行了，浪费我AC率...
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 16
using namespace std;
int n, m;
int g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int r[MAXN * MAXN][2];
int ex, ey, ix, iy;
bool flag = 0;
void dfs(int x, int y, int st){
if (x < 1 || x > n || y < 1 || y > m || g[x][y] == 0) return;
if (x == 2 && y == 5){
}
vis[x][y] = 1;
r[st][0] = x, r[st][1] = y;
if (x == ex && y == ey){
for (int i = 0; i < st + 1; i++){
printf("(%d,%d)", r[i][0], r[i][1]);
if (i != st) printf("->");
flag = 1;
}
printf("\n");
return;
}

if (!vis[x][y - 1]) dfs(x, y - 1, st + 1), vis[x][y - 1] = 0;
if (!vis[x - 1][y]) dfs(x - 1, y, st + 1), vis[x - 1][y] = 0;
if (!vis[x][y + 1]) dfs(x, y + 1, st + 1), vis[x][y + 1] = 0;
if (!vis[x + 1][y]) dfs(x + 1, y, st + 1), vis[x + 1][y] = 0;

}

int main(){
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
scanf("%d", &g[i][j]);
}
scanf("%d%d%d%d", &ix, &iy, &ex, &ey);
dfs(ix, iy, 0);
if (!flag) printf("-1");
return 0;
}
[/code]