5 solutions

  • 2
    @ 2024-3-13 13:07:47

    BFS大部分与点我查看相同

    思路

    • 反向查找,所以需要存储父节点

    代码

    #include<iostream>
#include<queue>
using namespace std;
int n=5,m=5;
bool g[114][514];
int vis[114][514];
int xl[4]={0,0,1,-1};
int yl[4]={1,-1,0,0};
struct node
{
	int x,y,t;
};
struct anno
{
	int data,fx,fy;//存储层数(其实这道题没必要,但我是复制的,不想改),父节点
};
anno ans[114][514];
queue<node >q;
int main()
{
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			cin>>g[i][j];
		}
	}
	q.push({0,0,1});
	vis[0][0]=1;
	int t=0;
	while(q.size())
	{
		node e=q.front();
		ans[e.x][e.y].data=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]==0 && x>=0 && x<n && y>=0 && y<m)//判断注意
			{
				vis[x][y]=1;
				q.push({x,y,e.t+1});
				ans[x][y].fx=e.x;//添加父节点
				ans[x][y].fy=e.y;//添加父节点
			}
		}
		q.pop();
	}
	vector<anno>vs;
	anno u=ans[n-1][m-1];//右下角
	vs.push_back(u);
	while(!(u.fx==0 && u.fy==0))//反向查找
	{
		u=ans[u.fx][u.fy];
		vs.push_back(u);
	}
	for(int i=vs.size()-1;i>-1;i--)
	{
		cout<<"("<<vs[i].fx<<", "<<vs[i].fy<<")\n";//输出
	}
	cout<<"("<<n-1<<", "<<m-1<<")\n";//右下角
	return 0;//完结散花
}
    • 1
      @ 2025-1-22 16:14:51 
      #include<bits/stdc++.h>

using namespace std;
char c[1001][1001];
bool vis[1001][1001];
struct node{
	int x,y,cnt;
};
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
node wks[1001][1001];
int bfs(){
	queue<node> q;
	vis[0][0]=1;
	q.push({0,0,1});
	while(!q.empty()){
		node we=q.front();
		int cx=we.x;
		int cy=we.y;
		q.pop();
		if(cx==5&&cy==5)return we.cnt;
		for(int i=0;i<4;i++){
			int nx=cx+dx[i];
			int ny=cy+dy[i];
			if(nx<0||ny<0||nx>=5||ny>=5||vis[nx][ny]==1||c[nx][ny]=='1')continue;
			vis[nx][ny]=1;
			wks[nx][ny]={cx,cy};
			q.push({nx,ny,we.cnt+1});
		}
	}
	return -1;
}
int main(){
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			cin>>c[i][j];
		}
	}
	bfs();
  //不懂可以自己来问我
	stack<node> kd;
	node xsd=wks[4][4];
	kd.push({4,4});
	while(xsd.x!=0||xsd.y!=0){
		kd.push({xsd.x,xsd.y});
		xsd=wks[xsd.x][xsd.y];
	}
	cout<<'('<<0<<", "<<0<<')'<<'\n';
	while(!kd.empty()){
		node fg=kd.top();
		kd.pop();
		cout<<'('<<fg.x<<", "<<fg.y<<')'<<'\n';
	}
	return 0;
}
      • 1
        @ 2024-3-12 20:04:58

        字数最多的代码（无实际意义）

        #include<iostream>
#include<queue>
#include<string>
using namespace std;
struct s{
	int x;
	int y;
	int z;
};
int out[100][2];
int a[50][50] = {};
bool vis[50][50] = {};
int fx[100][100] = {};
int fy[100][100] = {};
int sss;
queue<s> step;
int r=5,c=5;
int main()
{
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			cin >> a[i][j];
		}
	}
	s q1;q1.x=0;q1.y=0;q1.z=1; 
	step.push(q1);
	while(!step.empty()){
		//cout << step.front().x << " " << step.front().y << endl;
		if (step.front().x==r-1 && step.front().y==c-1){
			sss=step.front().z;
			break; 
		}
		vis[step.front().x][step.front().y]=1;
		s q;
		if (step.front().x+1<=r-1 && !vis[step.front().x+1][step.front().y] && a[step.front().x+1][step.front().y]==0){
			q.x=step.front().x+1;
			q.y=step.front().y;
			q.z=step.front().z+1;
			fx[step.front().x+1][step.front().y]=step.front().x;
			fy[step.front().x+1][step.front().y]=step.front().y;
			step.push(q);
		}
		if (step.front().x-1>=0 && !vis[step.front().x-1][step.front().y] && a[step.front().x-1][step.front().y]==0){
			q.x=step.front().x-1;
			q.y=step.front().y;
			q.z=step.front().z+1;
			fx[step.front().x-1][step.front().y]=step.front().x;
			fy[step.front().x-1][step.front().y]=step.front().y;
			step.push(q);
		}if (step.front().y+1<=c-1 && !vis[step.front().x][step.front().y+1] && a[step.front().x][step.front().y+1]==0){
			q.x=step.front().x;
			q.y=step.front().y+1;
			q.z=step.front().z+1;
			fx[step.front().x][step.front().y+1]=step.front().x;
			fy[step.front().x][step.front().y+1]=step.front().y;
			step.push(q);
		}
		if (step.front().y-1>=0 && !vis[step.front().x][step.front().y-1] && a[step.front().x][step.front().y-1]==0){
			q.x=step.front().x;
			q.y=step.front().y-1;
			q.z=step.front().z+1;
			fx[step.front().x][step.front().y-1]=step.front().x;
			fy[step.front().x][step.front().y-1]=step.front().y;
			step.push(q);
		}
		step.pop();
	}
	int i=r-1,j=c-1,nnt=0;
	while(sss){
		out[nnt][0]=i;
		out[nnt][1]=j;
		nnt++;
		int temp=fy[i][j];
		i=fx[i][j];j=temp;
		sss--;
	}
	nnt--;
	while(nnt){
		cout << "(" << out[nnt][0] << ", "  <<  out[nnt][1] << ")" << endl;
		nnt--;
	}
	cout << "(" << out[nnt][0] << ", "  <<  out[nnt][1] << ")" << endl;
	
 }
        • 1
          @ 2024-3-8 20:50:18

          题意

          和走迷宫差不多，只不过是要输出路径

          思路

          大体思路见题解 - 走迷宫

          就是这个思路把存层数换成存爸爸（上一个节点）

          代码

          #include <bits/stdc++.h>
using namespace std;
int cnt;
bool a[45][45],f[45][45];
int r,c;
struct pos{
	int x,y,fx,fy;	// f 是上一个点的位置
}fa[45][45];
vector<pos> p;
void bfs(){
	queue<pos> q;
	q.push({1,1,0,0});
	while(!q.empty()){
		int x = q.front().x,y = q.front().y;
		if (x == 5 && y == 5){	// 如果这个格子到了终点，直接退出
			return;
		}
		// 上
		if (a[x - 1][y] && !f[x - 1][y])	q.push({x - 1,y,x,y}),f[x - 1][y] = 1,fa[x - 1][y] = {x - 1,y,x,y};
		// 左
		if (a[x][y - 1] && !f[x][y - 1])	q.push({x,y - 1,x,y}),f[x][y - 1] = 1,fa[x][y - 1] = {x,y - 1,x,y};
		// 下
		if (a[x + 1][y] && !f[x + 1][y])	q.push({x + 1,y,x,y}),f[x + 1][y] = 1,fa[x + 1][y] = {x + 1,y,x,y};
		// 右
		if (a[x][y + 1] && !f[x][y + 1])	q.push({x,y + 1,x,y}),f[x][y + 1] = 1,fa[x][y + 1] = {x,y + 1,x,y};
		q.pop();	// 用完了，再见
	}
}
int main(int argc, char **argv){
	for (int i = 1;i <= 5;i++){
		for (int j = 1;j <= 5;j++){
			cin >> a[i][j];
			a[i][j] = !a[i][j];	// 这里路是 1，障碍是 0
		}
	}
	bfs();
	fa[1][1] = {1,1,0,0};
	int ix = 5,iy = 5;
	while (ix != 0 && iy != 0){
		p.push_back(fa[ix][iy]);
		int x = ix,y = iy;
		ix = fa[x][y].fx;
		iy = fa[x][y].fy;
	}
	reverse(p.begin(),p.end());	// 倒转数组
	for (int i = 0;i < p.size();i++){
		printf("(%d, %d)\n",p[i].x - 1,p[i].y - 1);
	}
	return 0;
}
          • -3
            @ 2024-3-12 13:52:23 
            #include<bits/stdc++.h>
using namespace std;
int k=0,c=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;
};
p a1[114][514];
p d[100000];
bool check(p a){
	if(w[a.x][a.y]=='0'&&!vis[a.x][a.y]&& a.x>=0 && a.x<5 && a.y>=0 && a.y<5){
		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==4&&a.y==4){
			//a1[4][4]=a;
			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);
				a1[p2.x][p2.y]=a;
			}
		}
	}
}
int main(){
	//cin>>r>>c;
	//cout<<"xxxxx";
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			cin>>w[i][j];
		}
	}
	bfs({0,0,1});
	int h=0;
	int x=4,y=4;
	while(a1[x][y].x!=0 || a1[x][y].y!=0){
			d[h]=a1[x][y];
			x=d[h].x;
			y=d[h].y;
			h++;
		}
	for(int i=h;i>=0;i--){
			cout<<"("<<d[i].x<<","<<" "<<d[i].y<<")"<<endl;
	}
	cout<<"("<<4<<","<<" "<<4<<")";
}
            • 1

            迷宫问题

            Information

            ID
            740
            Time
            1000ms
            Memory
            256MiB
            Difficulty
            6
            Tags
            # Submissions
            74
            Accepted
            21
            Uploaded By
            1. About
            2. Contact Us
            3. Privacy
            4. Terms of Service
            5. Copyright Complaint
            6. Language
            7. Legacy mode
            8. Theme
            2. 粤ICP备2022044963号-1
            3. Worker 0, 20ms
            4. Powered by Hydro v4.13.3 Community