迷宫问题 题解

给出一个(N*M)的迷宫图和一个入口、一个出口。
编一个程序，打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），白色方块的单元表示可以走（用0表示）。只能往上、下、左、右四个方向走。
如果有路则输出路径，否则输出no way.。

题解

还是比较简单的搜索板子题。
这里为了方便开了个pos结构体存储位置。

bfs的时候，每次扩大搜索面积，如果到了终点直接输出即可。
bfs使用了类链表的结构去存储并输出路径。


关于dfs，直接在搜索的过程中覆盖记录路径的prt数组即可。

bfs

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5 ;
typedef unsigned long long ull ;
typedef long long ll;
const int dir[5][2] = {{},{1,0},{-1,0},{0,1},{0,-1}};
int xa,xb,ya,yb,n,m; 
bool vis[N][N];
int pre[N][N][2];
struct pos{int x,y;};
void printbfs(int x,int y){
	if(!pre[x][y][1] && !pre[x][y][0]){
		printf("%d,%d
",x,y); 
		return;
	}
	printbfs(pre[x][y][0],pre[x][y][1]);
	printf("%d,%d
",x,y);
}
inline bool Edge(int x,int y){
	return (x < 1 || x > n || y < 1 || y > m || vis[x][y]);
}
inline void bfs(){
	queue<pos>q;
	q.push((pos){xa,ya});
	while(!q.empty()){
		pos u = q.front() ; q.pop();
		if(vis[u.x][u.y])continue;
		vis[u.x][u.y] = 1;
		if(u.x == xb && u.y == yb)break ;
		for(int d = 1 ; d <= 4 ; d ++){
			pos v = (pos){u.x + dir[d][0],u.y + dir[d][1]};
			if(!Edge(v.x,v.y))
				q.push(v),
				pre[v.x][v.y][0] = u.x,pre[v.x][v.y][1] = u.y;
		}
	}
	if(!pre[xb][yb][0] && !pre[xb][yb][1])printf("no way
");
	else printbfs(xb,yb);
}
signed main(){
	scanf("%d %d",&n,&m);
	int tem;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++)
			scanf("%d",&tem),
			vis[i][j] = tem == -1;
	scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
	bfs();
	return 0;
}

dfs

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5 ;
typedef unsigned long long ull ;
typedef long long ll;
const int dir[5][2] = {{},{1,0},{-1,0},{0,1},{0,-1}};
int xa,xb,ya,yb,n,m; 
bool vis[N][N];
int pre[N][N][2];
struct pos{int x,y;};
inline bool Edge(int x,int y){
	return (x < 1 || x > n || y < 1 || y > m || vis[x][y]);
}
int prt[10005][3],cnt;bool flag;
inline void printdfs(int x){
	for(int i = 0 ; i < x ; i ++)
		printf("%d,%d
",prt[i][0],prt[i][1]);
	flag = 1;
	return;
}
void dfs(int x,int y,int stp){
	if(x == xb && y == yb){
		printdfs(stp);
		return;
	}
	if(flag)return;
	pos u = (pos){x,y};
	for(int d = 1 ; d <= 4 ; d ++){
		pos v = (pos){u.x + dir[d][0],u.y + dir[d][1]};
		if(vis[v.x][v.y])continue;
		vis[v.x][v.y] = 1;
		prt[stp][0] = v.x,prt[stp][1] = v.y;
		dfs(v.x,v.y,stp + 1);
	}
}
signed main(){
	scanf("%d %d",&n,&m);
	int tem;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++)
			scanf("%d",&tem),
			vis[i][j] = tem == -1;
	scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
	prt[0][0] = xa,prt[0][1] = ya;
	dfs(xa,ya,1);
	if(!flag)printf("no way
");
	return 0;
}