bfs求助,0分
  • 板块P1301 魔鬼之城
  • 楼主Ch35
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/21 18:43
  • 上次更新2023/10/27 19:03:14
查看原帖
bfs求助,0分
672360
Ch35楼主2022/7/21 18:43

0分,3WA、7RE

#include<bits/stdc++.h>
using namespace std;
short a[10005][10005];
bool b[10005][10005];
int bs[10005][10005];
int n,m,x,y,z;
queue<int>xx;
queue<int>yy;
queue<int>zz;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    b[1][1]=1;
    xx.push(1);
    yy.push(1);
    zz.push(0);
    while(1){
        x=xx.front(),y=yy.front(),z=zz.front();
        if(z!=1&&(x-a[x][y]>0&&b[x-a[x][y]][y]==0&&(a[x-a[x][y]][y]!=0||x-a[x][y]==n&&y==m)))b[x-a[x][y]][y]=1,xx.push(x-a[x][y]),yy.push(y),bs[x-a[x][y]][y]=bs[x][y]+1;
        if(z!=2&&(y-a[x][y]>0&&b[x][y-a[x][y]]==0&&(a[x][y-a[x][y]]!=0||x==n&&y-a[x][y]==m)))b[x][y-a[x][y]]=1,xx.push(x),yy.push(y-a[x][y]),bs[x][y-a[x][y]]=bs[x][y]+1;
        if(z!=3&&(y+a[x][y]<=m&&b[x][y+a[x][y]]==0&&(a[x][y+a[x][y]]!=0||x==n&&y+a[x][y]==m)))b[x][y+a[x][y]]=1,xx.push(x),yy.push(y+a[x][y]),bs[x][y+a[x][y]]=bs[x][y]+1;
        if(z!=4&&(x+a[x][y]<=n&&b[x+a[x][y]][y]==0&&(a[x+a[x][y]][y]!=0||x+a[x][y]==n&&y==m)))b[x+a[x][y]][y]=1,xx.push(x+a[x][y]),yy.push(y),bs[x+a[x][y]][y]=bs[x][y]+1;
        if(z!=5&&(x-a[x][y]>0&&y-a[x][y]>0&&b[x-a[x][y]][y-a[x][y]]==0&&(a[x-a[x][y]][y-a[x][y]]!=0||x-a[x][y]==n&&y-a[x][y]==m)))b[x-a[x][y]][y-a[x][y]]=1,xx.push(x-a[x][y]),yy.push(y-a[x][y]),bs[x-a[x][y]][y-a[x][y]]=bs[x][y]+1;
        if(z!=6&&(x-a[x][y]>0&&y+a[x][y]<=m&&b[x-a[x][y]][y+a[x][y]]==0&&(a[x-a[x][y]][y+a[x][y]]!=0||x-a[x][y]==n&&y+a[x][y]==m)))b[x-a[x][y]][y+a[x][y]]=1,xx.push(x-a[x][y]),yy.push(y+a[x][y]),bs[x-a[x][y]][y+a[x][y]]=bs[x][y]+1;
        if(z!=7&&(x+a[x][y]<=n&&y-a[x][y]>0&&b[x+a[x][y]][y-a[x][y]]==0&&(a[x+a[x][y]][y-a[x][y]]!=0||x+a[x][y]==n&&y-a[x][y]==m)))b[x+a[x][y]][y-a[x][y]]=1,xx.push(x+a[x][y]),yy.push(y-a[x][y]),bs[x+a[x][y]][y-a[x][y]]=bs[x][y]+1;
        if(z!=8&&(x+a[x][y]<=n&&y+a[x][y]<=m&&b[x+a[x][y]][y+a[x][y]]==0&&(a[x+a[x][y]][y+a[x][y]]!=0||x+a[x][y]==n&&y+a[x][y]==m)))b[x+a[x][y]][y+a[x][y]]=1,xx.push(x+a[x][y]),yy.push(y+a[x][y]),bs[x+a[x][y]][y+a[x][y]]=bs[x][y]+1;
        if(x==n&&y==m){
            cout<<bs[x][y];
            return 0;
        }
        xx.pop(),yy.pop(),zz.pop();
        if(xx.empty()){
            cout<<"NEVER";
            return 0;
        }
    }
	return 0;
}

2022/7/21 18:43
加载中...