WHY 曾品林 help me
查看原帖
WHY 曾品林 help me
975630
woyaoAKIOI0924PTY楼主2024/12/19 21:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=160;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},sx,sy;
int n,m,a[N][N];
bool vis[N][N];
struct	Node{
	int x,y;
}path[N][N];
bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>m)
		return true;
	if(a[x][y]==1||vis[x][y])
		return true;
	return false;
}
void bfs(int sx,int sy)
{
	queue<Node> q;
	q.push({sx,sy});
	vis[sx][sy]=true;
	while(q.size())
	{
		Node t=q.front();
		q.pop();
		if(t.x==n&&t.y==m)
			return ;
		for(int i=0;i<4;++i)
		{
			int px=t.x+dx[i],py=t.y+dy[i];
			if(check(px,py))
				continue;
			vis[px][py]=true;
			path[px][py]={t.x,t.y};
			q.push({px,py});
		}
	}
} 	
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin>>a[i][j];
		}
	}
	bfs(0,0);
	if(path[n][m].x==0)
		cout<<"no way";
	else
	{
		vector<Node> ans;
		int x=n,y=m;
		while(true)
		{
			ans.push_back({x,y});
			int px=path[x][y].x,py=path[x][y].y;
			x=px,y=py;
			if(x==0||y==0)
				break;
		}
		for(int i=ans.size()-1;i>=0;--i)
		{
			cout<<ans[i].x<<" "<<ans[i].y<<endl;
		} 
	}
	return 0;
}
2024/12/19 21:59
加载中...