7.8总结 - 洛谷保存站

T628045 迷宫问题
分析：找到终点后倒着递归输出每个上一步的位置
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[105][105];
bool vis[105][105];
struct node{
	int x = 0;
	int y = 0;
};
int aa,bb;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
struct node1{
    int x;
    int y;
};
node1 pre[105][105];
void print(int x,int y){
	if(x == 0 and y == 0){
		cout << "(0, 0)" <<'\n';
		return ;
	}
	print(pre[x][y].x,pre[x][y].y);
	cout << '(' << x <<", "<< y << ')' << '\n';
}

void bfs(){
	queue<node> q;
	vis[0][0] = 1;
	q.push({0, 0});
	while(q.size()){
		node f = q.front();
		q.pop();
		if(f.x == 4 and f.y == 4){
			print(4,4);//找到了开始倒着输出
 			return ;
		}
		for(int i = 0;i < 4;i++){
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
			if(xx >= 0 and xx <= 4 and yy>= 0 and yy <= 4 and a[xx][yy] != '1' and vis[xx][yy] == 0){
				vis[xx][yy] = 1;
				pre[xx][yy] = {f.x,f.y};//记录上一步位置
				q.push({xx,yy});
			}
		}
	}
	
	return ;
}
int main(){
	
	
	for(int i = 0;i < 5;i++){//根据输入样例，下标从0开始
		for(int j = 0;j < 5;j++){
			cin >> a[i][j];
		}		
	}
	
	bfs();

return 0;
}

```
T628044 迷宫之输出路径-困难版
分析：和上一题类似，但加了个字符串
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[5500][5500];
char k[4] = {'D','L','R','U'};
bool vis[5500][5500];
struct node{
	int x;
	int y;
};
int aa,bb;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,-1,1,0};
struct node1{
    int x;
    int y;
    char c;
};
node1 pre[5500][5500];
void print(int x,int y){
	if(x == 0 and y == 0){
		return ;
	}
	print(pre[x][y].x,pre[x][y].y);
	cout << pre[x][y].c;
}

void bfs(){
	queue<node> q;
	vis[0][0] = 1;
	q.push({0, 0});
	while(q.size()){
		node f = q.front();
        
		q.pop();
		if(f.x == n-1 and f.y == m-1){//下标从0开始，故-1
			print(f.x,f.y);
 			return ;
		}
		for(int i = 0;i < 4;i++){
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
            //cout<<xx<<" "<<yy<<endl;
			if(xx >= 0 and xx < n and yy>= 0 and yy < m and a[xx][yy] != '1' and vis[xx][yy] == 0){
				vis[xx][yy] = 1;
				pre[xx][yy] = {f.x,f.y,k[i]};
				q.push({xx,yy});
			}
		}
	}
	cout << -1;
	return ;
}
int main(){
	cin >> n >> m;
	
	for(int i = 0;i < n;i++){//下表0开始
		for(int j = 0;j < m;j++){
			cin >> a[i][j];
		}		
	}
	
	bfs();

return 0;
}

```

P2360 地下城主
分析:三维的bfs,套路差不多，把二维的数组的换成三维即可
```cpp
#include<bits/stdc++.h>
using namespace std;
int l,r,c;
bool flag;
char a[35][35][35];
bool vis[35][35][35];
int dx[6]={1,-1,0,0,0,0};//上下前后左右
int dy[6]={0,0,-1,1,0,0};
int dz[6]={0,0,0,0,1,-1};
struct node{
	int x;
	int y;
	int z;
	int step;
};
int ax,bx,cx;
int bfs(){
	queue<node> q;
	vis[ax][bx][cx] = 1;//标记起点
	q.push({ax, bx, cx, 0});
	while(q.size()){
		node f = q.front();
		q.pop();

for(int i = 0;i < 6;i++){
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
			int zz = f.z + dz[i];
			if(a[xx][yy][zz] == 'E'){
   				return (f.step + 1);//找到了直接返回步数
			}	
			if(xx >= 1 and xx <= l and yy>= 1 and yy <= r and zz >= 1 and zz <= c and a[xx][yy][zz] != '#' and vis[xx][yy][zz] == 0 ){
				vis[xx][yy][zz] = 1;
				q.push({xx,yy,zz,f.step + 1});
			}
		}
	}
	
	return -1;
}

int main(){
	cin >> l >> r >> c;
	for(int k = 1;k <= l;k++){
		for(int i = 1;i <= r;i++){
			for(int j = 1;j <= c;j++){
				cin >> a[k][i][j];
				if(a[k][i][j] == 'S'){
					ax = k;
					bx = i;
					cx = j;		
				}
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sx,sy,fx,fy;
char a[15][15];
bool vis[15][15];
struct node{
	int x;
	int y;
	int step;
};
int aa,bb;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};

void bfs(){
	queue<node> q;
	vis[sx][sy] = 1;
	q.push({sx, sy,0});
	while(q.size()){
		node f = q.front();
		q.pop();
		if(a[f.x][f.y] == 'B'){
			cout << f.step - 1;
 			return ;
		}
		for(int i = 0;i < 4;i++){
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
			if(xx >= 1 and xx <= 10 and yy>= 1 and yy <= 10 and a[xx][yy] != 'R' and vis[xx][yy] == 0){
				vis[xx][yy] = 1;
				q.push({xx,yy,f.step+1});
			}
		}
	}
	return ;
}
int main(){

for(int i = 1;i <= 10;i++){//根据输入样例，下标从0开始
		for(int j = 1;j <= 10;j++){
			cin >> a[i][j];
			if(a[i][j] == 'L'){
				sx = i;
				sy = j;
			}
		}		
	}

bfs();

return 0;
}

```

}
		}
	}
	int x = bfs();	
	if(x != -1) cout<< "Escaped in " << x << " minute(s).";
	else cout <<"Trapped!"; 
	return 0;
}

```
作业
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sx,sy,fx,fy;
char a[155][155];
bool vis[155][155];
struct node{
	int x;
	int y;
};
int aa,bb;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
struct node1{
    int x;
    int y;
};
node1 pre[155][155];
void print(int x,int y){
	if(x == sx and y == sy){
		cout << '(' << sx<<','<< sy<< ')';
		return ;
	}
	print(pre[x][y].x,pre[x][y].y);
	cout << "->"<< '(' << x <<','<< y << ')' ;
} 
void bfs(){
	queue<node> q;
	vis[sx][sy] = 1;
	q.push({sx, sy});
	while(q.size()){
		node f = q.front();
		q.pop();
		if(f.x == fx and f.y == fy){
			print(f.x,f.y);
 			return ;
		}
		for(int i = 0;i < 4;i++){
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
			if(xx >= 1 and xx <= n and yy>= 1 and yy <= m and a[xx][yy] != '1' and vis[xx][yy] == 0){
				vis[xx][yy] = 1;
				pre[xx][yy] = {f.x,f.y};
				q.push({xx,yy});
			}
		}
	}
	cout << "no way";
	return ;
}
int main(){
	
	cin >> n >> m; 
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> a[i][j];
		}		
	}
	cin >> sx >> sy;
	cin >> fx >> fy;
	bfs();

return 0;
}

```
P1443
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x, y, step;
};

int m,n,x1,y2;

bool vis[410][410];
int step[410][410];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

//把能走的标记了
void dfs(int fx,int fy){
	queue <node> q;
	q.push({x1,y2,0});
	vis[x1][y2] = 1;
	while(q.size()){
		node f = q.front();
		q.pop();
		step[f.x][f.y] = f.step;
		
		for(int i = 0;i < 8;i++){ 
			int xx = f.x + dx[i];
			int yy = f.y + dy[i];
			if(xx > 0 and xx <= n and yy > 0 and yy <= m and vis[xx][yy] == 0){
				q.push({xx ,yy , f.step + 1});
				vis[xx][yy] = 1; 
			}
			  
		} 
	}
	
	return;
}
int main(){
	cin >> n >> m >> x1 >> y2;
	dfs(x1,y2);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(vis[i][j]) cout << ' '<< step[i][j];
			else cout << ' '<<-1;
		}
		cout << '\n';
	}
	return 0;
}
```
P1699 [USACO19OPEN] Bucket Brigade B

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sx,sy,fx,fy;
char a[15][15];
bool vis[15][15];
struct node{
	int x;
	int y;
	int step;
};
int aa,bb;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};

for(int i = 1;i <= 10;i++){
		for(int j = 1;j <= 10;j++){
			cin >> a[i][j];
			if(a[i][j] == 'L'){
				sx = i;
				sy = j;
			}
		}		
	}

bfs();

return 0;
}

```

正在渲染内容...