10分!!大佬求调
  • 板块P1238 走迷宫
  • 楼主godogod
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 16:00
  • 上次更新2024/8/7 16:38:24
查看原帖
10分!!大佬求调
1067504
godogod楼主2024/8/7 16:00
#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[]={1,0,-1,0};
int dy[]={0,1,0,-1};
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/7 16:00
加载中...