1 条题解

  • 0
    @ 2023-8-8 15:48:22
    #include<bits/stdc++.h>
    using namespace std;
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0},xy[40010][3],pre[40010],n,m,qdx,qdy,zdx,zdy;
    bool a[160][160];
    void print(int n,bool flag)
    {
    	if(pre[n])print(pre[n],1);
    	cout<<'('<<xy[n][1]<<','<<xy[n][2]<<')';
    	if(flag)cout<<"->";
    }
    void bfs()
    {
    	int head=0,tail=1;
    	xy[1][1]=qdx;
    	xy[1][2]=qdy;
    	a[qdx][qdy]=1;
    	pre[1]=0;
    	while(head<tail)
    	{
    		head++;
    		for(int i=0;i<4;i++)
    		{
    			int x=xy[head][1]+dx[i];
    			int y=xy[head][2]+dy[i];
    			if(x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
    			{
    				tail++;
    				xy[tail][1]=x;
    				xy[tail][2]=y;
    				pre[tail]=head;
    				a[x][y]=1;
    				if(x==zdx&&y==zdy)
    				{
    					print(tail,0);
    					exit(0);
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			cin>>a[i][j];
    	cin>>qdx>>qdy>>zdx>>zdy;
    	bfs();
    	cout<<"no way";
    	return 0;
    }
    
    • 1

    信息

    ID
    107
    时间
    1000ms
    内存
    120MiB
    难度
    8
    标签
    递交数
    12
    已通过
    11
    上传者