0831-C06BFS

1. 广度优先搜索

#include <bits/stdc++.h>
#include <queue>
using namespace std;

struct node{
	int x, y, steps;
};

char mp[105][105];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};	//方向数组 
bool vis[105][105]; 
int n, m, T; 

queue<node> q;	//队列 

//维护队列, 从第一个点开始搜索 
int bfs(){
	
	while (q.size()) {
		node t = q.front();	//搜索的第一个点
		q.pop();
		if (mp[t.x][t.y] == 'E'){
			return t.steps; 
		} 
		for(int i=0; i<4; i++){
			int a = t.x + dir[i][0];
			int b = t.y + dir[i][1];
			if (vis[a][b]==1 || mp[a][b] == '#') continue;
			q.push((node){a, b, t.steps + 1});
			vis[a][b] = 1; 
		} 
	}
	return -1;
} 

int main(){
	cin >> T;
	while (T--){
		memset(mp, '#', sizeof (mp));
		memset(vis, 0, sizeof (vis));
		cin >> n >> m;
		for (int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cin >> mp[i][j];
				if (mp[i][j] == 'S'){
					vis[i][j] = 1; 
					q.push((node){i, j, 0}); 
				}
			} 
		}
		cout << bfs() << endl;
	}
	
	return 0;
}

2. 马的遍历

#include <queue>
#include <bits/stdc++.h>
using namespace std;

struct node{
	int x, y, steps; 
};
int dx[8] = {1,1,2,2,-1,-1,-2,-2};
int dy[8] = {2,-2,1,-1,2,-2,1,-1};
int vis[405][405], n, m, x, y;
queue<node> q;

int main(){
	memset(vis, -1, sizeof vis);
	cin >> n >> m >> x >> y;
	q.push({x, y, 0});
	vis[x][y] = 0;	//马的起始位置为 0
	
	while (q.size()) {
		node t = q.front();
		q.pop();
		for (int i=0; i<8; i++){
			int a = t.x + dx[i];	//x方向拓展 
			int b = t.y + dy[i];	//y方向拓展 
			if (vis[a][b] != -1) continue;
			if (a<1 || a>n || b<1 || b>m) continue;
			q.push({a, b, t.steps + 1}); 
			vis[a][b] = t.steps + 1; 
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			printf("%-5d", vis[i][j]);
		}
		cout << endl; 
	}

	return 0;
}

3. practice

#include <bits/stdc++.h>
using namespace std;

int n, m, t, ans;
int sx, sy, fx, fy; 
int mtx[105][105], vis[105][105];
int dir[4][2] = {1,0,0,1,-1,0,0,-1}; 


void dfs(int x, int y){
	if (x==fx && y==fy) 	//如果找到出口, 那么结束 
	{
		ans++;
		return ;
	}
	//朝不同方向进行拓展 
	for (int i=0; i<4; i++){
		int nx = x + dir[i][0], ny = y + dir[i][1];
		if (nx<1 || nx>n ||ny<1 || ny>m)  continue; 
		if (mtx[nx][ny]==1 || vis[nx][ny])  continue;	//如果新的点不满足搜索条件那么跳过 
		vis[nx][ny] = 1; 	//标记搜索点 
		dfs(nx, ny); 
		vis[nx][ny] = 0; 	//回溯思想 (复原) 
	}
} 

int main(){
	scanf("%d%d%d", &n, &m, &t);
	scanf("%d%d%d%d", &sx, &sy, &fx, &fy);
	while (t--){
		int x, y;
		scanf("%d%d", &x, &y);
		mtx[x][y] = 1;		//1是障碍物 
	} 
	
	vis[sx][sy] = 1;
	dfs(sx, sy); 
	printf("%d", ans); 

	return 0;
}