曾老师公认的标准学习代码,huang*zhe的不是哦!

题意

• 求出从左上角到右下角的最少步数

思路

• 用广度优先(深度也可以,但标准是广度优先)
• 广度优先是在二维数组中循环每个坐标
• 所以,需要一个结构体存储$x$,$y$和层数
• $g$用于存储输入的图的每个点
• $vis$用于标记是否走过
• $ans$用于存储每个点最少的步数
• 遍历上下左右的点需要判断以下
  • 是否标记过
  • 是 "."
  • 点是否在边界内
• 上下左右最好用相对坐标

代码

#include<iostream>
#include<queue>
using namespace std;
int n,m;
char g[114][514];//输入的图
int vis[114][514];//标记数组
int ans[114][514];//每个点的步数
int xl[4]={0,0,1,-1};//x方位数组
int yl[4]={1,-1,0,0};//y方位数组
struct node
{
	int x,y,t;//结构体存储
};
queue<node >q;//BFS经典队列
int main()
{
	cin>>n>>m;//输入
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>g[i][j];//输入
		}
	}
	q.push({0,0,1});//根
	vis[0][0]=1;//标记
	while(q.size())//不为空时
	{
		node e=q.front();
		ans[e.x][e.y]=e.t;//记录步数
		for(int i=0;i<4;i++)
		{
			int x=e.x+xl[i],y=e.y+yl[i];
			if(!vis[x][y] && g[x][y]=='.' && x>=0 && x<n && y>=0 && y<m)//繁琐的判断
			{
				vis[x][y]=1;//标记
				q.push({x,y,e.t+1});//入队
			}
		}
		q.pop();//出队
	}
	cout<<ans[n-1][m-1];//输出
	return 0;//完结散花
}

BFS

#include<bits/stdc++.h>
using namespace std;
struct s{
    int x,y,num;
};
int r,c;
queue<s> q;
int fx[9]={1,0,-1,0},fy[9]={0,1,0,-1};
string arr[110];
int main(){
    cin>>r>>c;
    for(int i=0;i<r;i++){
        cin>>arr[i]; 
    }
    s aaa={0,0,1};
    q.push(aaa);
    arr[0][0]='#';
    while(q.size()){
        s b=q.front();
        if(b.x==r-1 && b.y==c-1){
            cout<<b.num;
            return 0;
        }
        for(int i=0;i<4;i++){
            s bbb;
            bbb.x=b.x+fx[i];
            bbb.y=b.y+fy[i];
            bbb.num=b.num+1;
            if(bbb.x<r && bbb.x>=0 && bbb.y<c && bbb.y>=0 && arr[bbb.x][bbb.y]!='#') 
                q.push(bbb),arr[bbb.x][bbb.y]='#';
        }
        q.pop();
    }
    return 0;
}

背景

老师不准让我们用 DFS，只能用 BFS

题意

找到左上角到右下角的最快路径

思路

用 BFS 的话...

首先开结构体存 $x$、$y$、层数，然后遍历上下左右。如果这格到终点，就输出

代码

#include <bits/stdc++.h>
using namespace std;
int a[45][45],cnt;
bool f[45][45];
int r,c;
struct pos{
	int x,y,ceng;
};
void bfs(){
	queue<pos> q;
	q.push({1,1,1});
	while(!q.empty()){
		int x = q.front().x,y = q.front().y,ceng = q.front().ceng;
		if (x == r && y == c){	// 如果这个格子到了终点，直接退出
			cnt = ceng;
			return;
		}
		// 上
		if (a[x - 1][y] && !f[x - 1][y])	q.push({x - 1,y,ceng + 1}),f[x - 1][y] = 1;
		// 左
		if (a[x][y - 1] && !f[x][y - 1])	q.push({x,y - 1,ceng + 1}),f[x][y - 1] = 1;
		// 下
		if (a[x + 1][y] && !f[x + 1][y])	q.push({x + 1,y,ceng + 1}),f[x + 1][y] = 1;
		// 右
		if (a[x][y + 1] && !f[x][y + 1])	q.push({x,y + 1,ceng + 1}),f[x][y + 1] = 1;
		q.pop();	// 用完了，再见
	}
}
int main(int argc, char **argv){
	cin >> r >> c;
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			char c;
			cin >> c;
			a[i][j] = (c == '.'?1:0);	// 这里路是 1，障碍是 0
		}
	}
	bfs();
	cout << cnt;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int r, c;
bool vis[45][45];
int dx[4]={-1, 1, 0, 0};
int dy[4]={0, 0, 1, -1};
struct node
{
	int xx, yy, s;
};

int bfs(int x, int y)
{
	vis[1][1]=true;
	queue<node> q;
	q.push({x, y, 1});
	while(!q.empty())
	{
		int cx=q.front().xx;
		int cy=q.front().yy;
		int steps=q.front().s;
		q.pop();//用完了扔掉 
		if(cx==r&&cy==c)
		{
			return steps;
		}
		for(int i = 0; i < 4; i++)
		{
			int nx=cx+dx[i];
			int ny=cy+dy[i];
			if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&!vis[nx][ny])
			{
				q.push({nx, ny, steps+1});
				vis[nx][ny]=true;
			}
		}
	}
}
int main()
{
	cin >> r >> c;
	for(int i = 1; i <= r; i++)
	{
		for(int j = 1; j <= c; j++)
		{
			char n;
			cin >> n;
			if(n=='#')//不能走
			{
				vis[i][j]=true;
			}
		}
	}
	int ans=bfs(1, 1);
	cout << ans;
	
	return 0;
} 

12###
#3456
#4#6#
#5#7#
#6#89

#include<bits/stdc++.h>
using namespace std;
struct site{
	int x,y;
	int cnt;	//计数
};
queue<site> bvis;
int r,c,cnt=0;
bool maze[45][45];
int x_move[8]={0,0,-1,1,-1,1,-1,1};
int y_move[8]={1,-1,0,0,1,1,-1,-1};

void bfs(){
	while(!bvis.empty()){	//while(1)虽然能过，但数据改改就RE了
		site t=bvis.front();
		if(t.x == r && t.y == c){	//访问到右下角就退出
			return ;
		} 
		for(int i=0;i<4;i++){	
			int mx=t.x+x_move[i], my=t.y+y_move[i];  //向上下左右移动
			if(maze[mx][my] && mx>=1 && mx<=r && my>=1 && my<=c){
				bvis.push({mx,my,t.cnt+1});
				maze[mx][my]=0;		//走过的空格子与有障碍物的格子都记为不能走
				
			}
		}
		bvis.pop();
	}
}

int main(){
	char a;
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a;
			if(a == '.') maze[i][j]=1;
			else maze[i][j]=0;
		}
	}
	maze[1][1]=0;	
	bvis.push({1,1,1});		//记得初始化
	bfs();
	cout<<bvis.front().cnt;
	return 0;
}

bfs真好用

#include<bits/stdc++.h>
using namespace std;
int n,m;
char ppp[114][514];
int pppp[114][514],ppppp[114][514],xl[4]={0,0,1,-1},yl[4]={1,-1,0,0};
struct node{
	int x,y,t;
};
queue<node>q;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>ppp[i][j];
	q.push({0,0,1});
	pppp[0][0]=1;
	while(q.size()){
		node pp=q.front();
		ppppp[pp.x][pp.y]=pp.t;
		for(int i=0;i<4;i++){
			int x=pp.x+xl[i],y=pp.y+yl[i];
			if(!pppp[x][y]&&ppp[x][y]=='.'&&x>-1&&x<n&&y>-1&&y<m){
				pppp[x][y]=1;
				q.push({x,y,pp.t+1});
			}
		}
		q.pop();
	}
	cout<<ppppp[n-1][m-1];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
char a[100][100];
struct node{
	int x,y,ste;
};
int dx[]={-1,0,1,0},
	dy[]={0,1,0,-1};
bool vis[100][100];
queue<node> q;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	vis[1][1]=true;
	q.push({1,1,1});
	while(!q.empty())
	{
		node t=q.front();
		q.pop();
		if(t.x==n&&t.y==m)
		{
			cout<<t.ste<<endl;
			return 0;
		}
		for(int i=0;i<4;i++)
		{
			int xx=t.x+dx[i],yy=t.y+dy[i],st=t.ste+1;
			if(a[xx][yy]!='#'&&!vis[xx][yy]&&xx>=1&&xx<=n&&yy>=1&&yy<=m)
			{
				vis[xx][yy]=true;
				q.push({xx,yy,st});
			}
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int r,c;
int k=0;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int vis[10005][10005];
char w[101][101];
struct p{
	int x,y,t;
};
bool check(p a){
	if(w[a.x][a.y]=='.'&&!vis[a.x][a.y]&& a.x>=1 && a.x<=r && a.y>=1 && a.y<=c){
		vis[a.x][a.y]=1;
		return true;
	}
	else{
		return false;
	}
}
void bfs(p s){
	queue<p> q;
	q.push(s);
	//cout<<s.x<<" "<<s.y<<"\n";
	while(!q.empty()){
		p a=q.front();
		q.pop();
		//cout<<a.x<<" "<<a.y<<"\n";
		if(a.x==r&&a.y==c){
			cout<<a.t;
			return;
		}
		for(int i=0;i<4;i++){
			int nx=a.x+dx[i];
			int ny=a.y+dy[i];
			p p2={nx,ny,a.t+1};
			if(check(p2)){
				q.push(p2);
			}
		}
	}
}
int main(){
	cin>>r>>c;
	//cout<<"xxxxx";
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>w[i][j];
		}
	}
	bfs({1,1,1});
	

我爱打表

#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout << 69; 
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a,b;
bool vst[45][45]={};
char aa[45][45];
struct mg{
	int a1,a2;
	int stp;
};
int move1[4]={0,0,1,-1};
int move2[4]={1,-1,0,0};
ll bfs(){
	queue<mg> q;
	q.push({0,0,1});
	vst[0][0]=true;
	while(!q.empty()){
		mg k=q.front();
		q.pop();
		if(k.a1==a-1&&k.a2==b-1) return k.stp;
		for(int i=0;i<4;i++){
			int mv1=k.a1+move1[i];
			int mv2=k.a2+move2[i];
			if(mv1>=0&&mv2>=0&&mv1<a&&mv2<b&&aa[mv1][mv2]!='.'&&!vst[mv1][mv2]){
				vst[mv1][mv2]=true;
				q.push({mv1,mv2,k.stp+1});
			}
		}
	}
	return 69;
}
int main(){
	cin>>a>>b;
	for(int i=0;i<a;i++) for(int j=0;j<b;j++) cin>>aa[i][j];
	cout<<bfs()<<"\n";
	return 0;
}

无坑