90分,RE on #7
查看原帖
90分,RE on #7
939189
Eternal_violin楼主2024/8/10 15:01
#include<bits/stdc++.h>
using namespace std;
struct SGYQ{
    int x,y,sp,fp;
};
char mp[2010][2010];
bool P[2010][2010][2];
int n,m,ax,ay,f,dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
void bfs(){
	queue<SGYQ>q;
	SGYQ t,Tp;
    t.fp=0;t.sp=0;t.x=1;t.y=1;
    q.push(t);
    P[1][1][0]=true;
    while(!q.empty()){
        t=q.front();
        q.pop();
        if(t.fp==1)f=1;
        else f=0;
        for(int i=0;i<4;i++){
        	SGYQ xp;
            xp.x=dx[i]+t.x,xp.y=dy[i]+t.y;
            if(xp.x>0&&xp.x<=n&&xp.y>0&&xp.y<=m&&mp[xp.x][xp.y]!='#'&&!P[xp.x][xp.y][f]){
                if(xp.x==n&&xp.y==m){
                    cout<<t.sp+1;
                    return ;
                }
                P[xp.x][xp.y][f]=true;
                Tp.fp=f;Tp.sp=t.sp+1;
                Tp.x=xp.x;Tp.y=xp.y;
                q.push(Tp);
            }
        }
        SGYQ xp;
        xp.x=t.x+dx[4],xp.y=t.y+dy[4];
        if(f==0&&!P[xp.x][xp.y][1]&&xp.x>0&&xp.x<=n&&xp.y>0&&xp.y<=m&&mp[xp.x][xp.y]!='#'){
            if(xp.x==n&&xp.y==m){
                cout<<t.sp+1;
                return ;
            }
            P[xp.x][xp.y][1]=true;
            Tp.fp=1;Tp.sp=t.sp+1;
            Tp.x=xp.x;Tp.y=xp.y;
            q.push(Tp);
        }
    }
    cout<<-1;
}
int main(){
	cin>>n>>m>>dx[4]>>dy[4];
	for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    bfs();
    return 0;
}
2024/8/10 15:01
加载中...