10pts求助
  • 板块P1238 走迷宫
  • 楼主godogod
  • 当前回复22
  • 已保存回复22
  • 发布时间2024/8/24 14:34
  • 上次更新2024/8/24 16:41:47
查看原帖
10pts求助
1067504
godogod楼主2024/8/24 14:34
#include<bits/stdc++.h>
using namespace std;
int m,n,sum=0;
int map_[25][25]; 
int head,tail;
int sx,sy,ex,ey;//起始点和终点 
struct node
{
    int x,y,pre;
}que[10005];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
bool jud[25][25];

void print(int k)
{
    if(k==0) return;
    print(que[k].pre);
    cout << "(" << que[k].x << "," << que[k].y << ")->";
}

bool BFS(int sx, int sy)
{
    head=0,tail=1;
    que[head].x=sx;
    que[head].y=sy;
    que[head].pre=0;
    jud[sx][sy]=false;
    while(head < tail)
    {
        head++;
        for(int i=0;i<4;i++)
        {
            int xx=que[head].x+dx[i];
            int yy=que[head].y+dy[i];
            if(xx>=1 && xx<=m && yy>=1 && yy<=n && map_[xx][yy]==1 && jud[xx][yy]==true)
            {
                tail++;
                que[tail].x=xx;
                que[tail].y=yy;
                que[tail].pre=head;
                jud[xx][yy]=false;
                if(xx==ex && yy==ey)
                {
                    print(tail);
                    cout << "(" << xx << "," << yy << ")" << endl;
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(jud,true,sizeof(jud));
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>map_[i][j];
            if(map_[i][j]==1)sum++;
        }
    }
    
    cin>>sx>>sy>>ex>>ey;
    if(BFS(sx, sy))
    {
        cout << "(1,1)->";
        print(1);
    }
    else
    {
        cout << "-1";
    }
    return 0;
}
2024/8/24 14:34
加载中...