求助P1825 宽搜最短路问题
  • 板块学术版
  • 楼主Bread_m
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/17 21:41
  • 上次更新2023/10/27 02:35:57
查看原帖
求助P1825 宽搜最短路问题
362558
Bread_m楼主2022/11/17 21:41

已AC,但自测数据加上#8数据对比有问题 其实我并没有对

搜索初学蒻鸡,无法自解

本人代码如下

#include<bits/stdc++.h> 
using namespace std;
char mp[302][302]; 
int mmp[302][302];
bool bj[302][302];
int d[100000][2],
    dx[4]={-1,1,0,0},
    dy[4]={0,0,-1,1};
int n,m;

int change(int &x,int &y)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!(i==x&&j==y))
            {
                if(mp[i][j]==mp[x][y])
                {

                    x=i;
                    y=j;
                    return 0;
                }
            }
        }
    }
}
bool asd[26];
void bfs(int x,int y){
    int head=0,tail=1;
    d[tail][0]=x,d[tail][1]=y;
    bj[x][y]=true;
    do{
        head++;
        int xn=d[head][0],yn=d[head][1];
        if(mp[xn][yn]>='A'&&mp[xn][yn]<='Z'){
            int z=mmp[xn][yn];

            change(xn,yn);

            mmp[xn][yn]=z;
        }
        for(int i=0;i<4;i++){
            int nx=xn+dx[i],ny=yn+dy[i];
            if((mp[nx][ny]!='#')&&(!bj[nx][ny])){
                bj[nx][ny]=true;
                tail++;
                d[tail][0]=nx;
                d[tail][1]=ny;
                mmp[nx][ny]=mmp[xn][yn]+1;
                if(mp[nx][ny]=='=') {
                    cout << mmp[nx][ny];
                    return ;
                }

            }
        }

    }while(head<tail);
}

int main(){
    cin >> n >> m;
    int x,y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c; cin >> c;
            if(c=='@') x=i,y=j;
            mp[i][j]=c;
        }
    }
    bfs(x,y);
    return 0;
}

#8的数据如下

8 6
###=##
#..W.#
#....#
##@..#
#....#
#....#
#..W.#
######

依照本人设置的入队顺序 dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; 即 ↓ ↑ ← →的入队顺序 是没有问题的,跑出来的值图是酱紫:

000500
032440
021230
000120
021230
032340
043440
000000

完全没有问题,但如果把入队顺序换一下,如 dx[4]={1,-1,0,0}, dy[4]={0,0,-1,1};即 变为 ↑ ↓ ← →的入队顺序,跑出来就是:

000400
032340
021230
000120
021230
032340
043340
000000

可见,若非恰好在此数据下程序先从下方入队了传送门,我的程序会直接无视上方的传送门在第四步的时候就到达终点,不知道是什么问题....望各位大佬帮忙看看

┭┮﹏┭┮

2022/11/17 21:41
加载中...