wa8 90分求助
查看原帖
wa8 90分求助
494405
tqz1013楼主2021/11/11 13:38
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;

int n,m;
int sx,sy,ex,ey,sdt;
char c;
const int N = 60;
int g[N][N],dist[N][N][4];
struct node{
    int x,y,dt;
};
int dx[] = {-1,0,1,0},dy[]={0,-1,0,1};

bool check(int x,int y,int dt)
{
    if(dist[x][y][dt]!=0x3f3f3f3f)return false;
    if(x>=n||x<=0||y>=m||y<=0)return false;
    if(g[x-1][y-1]==1||g[x-1][y]==1||g[x][y-1]==1||g[x][y]==1)return false;
    return true;
}
int bfs()
{  
   queue<node> q;
   memset(dist,0x3f,sizeof dist);
   q.push({sx,sy,sdt});
   dist[sx][sy][sdt]=0;
   
   while(q.size())
   {
       auto t = q.front();
       q.pop();
       int x = t.x,y=t.y,dt=t.dt;
       bool a1=false,a2=false;
       if(check(x+dx[dt],y+dy[dt],dt))
       {
           dist[x+dx[dt]][y+dy[dt]][dt]=dist[x][y][dt]+1;
           q.push({x+dx[dt],y+dy[dt],dt});
           a1=true;
       }
       if(check(x+2*dx[dt],y+2*dy[dt],dt)&&a1)
       {
           dist[x+2*dx[dt]][y+2*dy[dt]][dt]=dist[x][y][dt]+1;
           q.push({x+2*dx[dt],y+2*dy[dt],dt});
           a2=true;
       }
       if(check(x+3*dx[dt],y+3*dy[dt],dt)&&a2)
       {
           dist[x+3*dx[dt]][y+3*dy[dt]][dt]=dist[x][y][dt]+1;
           q.push({x+3*dx[dt],y+3*dy[dt],dt});
       }
       if(check(x,y,(dt+1)%4))
       {
           dist[x][y][(dt+1)%4]=dist[x][y][dt]+1;
           q.push({x,y,(dt+1)%4});
       }
       if(check(x,y,(dt+3)%4))
       {
           dist[x][y][(dt+3)%4]=dist[x][y][dt]+1;
           q.push({x,y,(dt+3)%4});
       }
   }
   
   int minv = 0x3f3f3f3f;
   for(int i=0;i<4;i++)
   minv = min(minv,dist[ex][ey][i]);
   
   if(minv==0x3f3f3f3f)return -1;
   else return minv;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
     scanf("%d",&g[i][j]);
     
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    scanf(" %c",&c);
    if(c=='N')sdt=0;
    else if(c=='W')sdt=1;
    else if(c=='S')sdt=2;
    else sdt=3;
    printf("%d\n",bfs());
    return 0;
}
2021/11/11 13:38
加载中...