图论之dfs与bfs的练习

dfs--深度优选搜索

bfs--广度优先搜索

迷宫问题--dfs

问题：

给定一个n*m的二维迷宫数组其中S是起点，T是终点，*是墙壁（无法通过）， .是道路

问从起点S出发沿着上下左右四个方向走，能否走到T点？能输出"YES",否则输出"NO"。

8 8

*****...

*.S...**

*****.**

*****..*

*T..**.*

.**.**.*

..*....*

...*****

#include
using namespace std;
const int N = 1e4 + 10;
char g[N][N];//迷宫数组
bool vis[N][N];//二维标记数组
//方向数组
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int n, m;
int sx, sy, tx, ty;
bool flag;
void dfs(int px, int py) {
	//如果当前搜的点p是终点点t，终止搜索
	if (px == tx && py == ty) {
		flag = true;
		return;
	}
	//沿着点p的邻接点继续搜索
	for (int i = 0; i > n >> m;
	for (int i = 1; i  g[i][j];
			if (g[i][j] == 'S') sx = i, sy = j;//找到起点的坐标
			if (g[i][j] == 'T') tx = i, ty = j;//找到终点的坐标
		}
	}
	vis[sx][sy] = 1;
	flag = false;
	dfs(sx, sy);
	if (flag) cout  t;
	while (t--) {
		cin >> n;
		for (int i = 1; i  g[i][j];  
		cin >> sx >> sy >> tx >> ty;
		sx++, sy++, tx++, ty++;//注意:本题下标从0开始
		//多组数据要将相关状态重置
		flag = false;
		memset(vis, 0, sizeof vis);//将vis数组全体清0
		vis[sx][sy] = 1;
		dfs(sx, sy);
		if (flag) cout  n;
		for (int i = 1; i  g[i][j];   /*scanf(" %c", &g[i][j]); */
		cin >> sx >> sy >> tx >> ty;
		sx++, sy++, tx++, ty++;//注意本题下标从0开始
		//多组数据要将相关状态重置
		flag = false;
		memset(vis, 0, sizeof vis);//将vis数组全体清0
		vis[sx][sy] = 1;
		bfs({sx, sy});
		if (flag) cout  w && w && h)//注意要判断w和h都为0结束
	{
		for (int i = 1; i  g[i][j];
				if (g[i][j] == '@')
					sx = i, sy = j;
			}
		}
		//多组数据注意相关状态
		cnt = 1;
		memset(vis, 0, sizeof vis);//vis数组全体清0
		vis[sx][sy] = 1;
		dfs(sx, sy);
		cout  h >> w && w && h)//注意要判断w和h都为0结束
	{
		for (int i = 1; i  g[i][j];
				if (g[i][j] == '@')
					sx = i, sy = j;
			}
		}
		//多组数据注意相关状态
		cnt = 1;
		memset(vis, 0, sizeof vis);//vis数组全体清0
		vis[sx][sy] = 1;
		dfs({ sx, sy });
		cout  t;
	while (t--)
	{
		cin >> n >> m;
		//多组数据相关状态清空
		cnt =0;
		cin >> sx >> sy;
		sx++, sy++;
		memset(vis, 0, sizeof vis);
		vis[sx][sy] = 1;
		dfs(sx, sy,1);//起点是第一层，最后应该走到n*m层结束
		cout  n >> m;
	for (int i = 1; i  g[i][j];
		}
	}
	vis[g[1][1]] = 1;
	dfs(1,1,1);
	cout > n >> m && n && m) {
		for (int i = 1; i  g[i][j];
				if (g[i][j] == '@') sx = i, sy = j;
				if (g[i][j] == '*') tx = i, ty = j;
			}
		}
		ans = -1;
		memset(vis, 0, sizeof vis);
		bfs({ sx,sy,1 });
		cout  sx>>sy;
		memset(vis, 0, sizeof vis);
		bfs({ sx, sy ,1});
		cout > t;
	while (t--)
	{
		cin >> n;
		cin >> sx >> sy >> tx >> ty;
		sx++, sy++,tx++, ty++;
		ans = 0;
		memset(vis, 0, sizeof vis);
		dfs({ sx, sy,1 });
		cout