P1126-机器人搬重物

男娘i 2023-06-01 08:48 33阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = a;i < b;i ++)
     3 #define maxn 52
     4 #define INF 0x3f3f3f3f
     5 using namespace std;
     6 int m,n;
     7 int mp[maxn][maxn];
     8 int vis[maxn][maxn][4];
     9 int dx[] = {-1,0,1,0};
    10 int dy[] = {
        0,-1,0,1};
    11 struct P
    12 {
    13     int x;
    14     int y;
    15     int dr;
    16 };
    17 P st,ed;
    18 
    19 bool valid(P p)
    20 {
    21     if(p.x>0 && p.y>0 && p.x<m && p.y<n && mp[p.x][p.y]==0)
    22         return true;
    23     return false;
    24 }
    25 
    26 int bfs()
    27 {
    28     queue<pair<P,int>> q;
    29     q.push({st,0});
    30     vis[st.x][st.y][st.dr] = 0;
    31     while(!q.empty())
    32     {
    33         pair<P,int> nw = q.front();
    34         q.pop();
    35         P np = nw.first;
    36         P tp;
    37 
    38         tp = np;
    39         tp.dr = (np.dr+3)%4;
    40         if(valid(tp) && nw.second+1<vis[tp.x][tp.y][tp.dr])
    41         {
    42             vis[tp.x][tp.y][tp.dr] = nw.second+1;
    43             q.push({tp,nw.second+1});
    44         }
    45 
    46         tp = np;
    47         tp.dr = (np.dr+5)%4;
    48         if(valid(tp) && nw.second+1<vis[tp.x][tp.y][tp.dr])
    49         {
    50             vis[tp.x][tp.y][tp.dr] = nw.second+1;
    51             q.push({tp,nw.second+1});
    52         }
    53 
    54         tp = np;
    55         _for(i,0,3)
    56         {
    57             tp.x += dx[np.dr];
    58             tp.y += dy[np.dr];
    59             if(!valid(tp))
    60                 break;
    61             if(nw.second+1<vis[tp.x][tp.y][tp.dr])
    62             {
    63                 vis[tp.x][tp.y][tp.dr] = nw.second+1;
    64                 q.push({tp,nw.second+1});
    65             }
    66         }
    67     }
    68     return min(vis[ed.x][ed.y][3],min(vis[ed.x][ed.y][2],min(vis[ed.x][ed.y][1],vis[ed.x][ed.y][0])));
    69 }
    70 int main()
    71 {
    72     memset(mp,0,sizeof(mp));
    73     memset(vis,INF,sizeof(vis));
    74     scanf("%d%d",&m,&n);
    75     _for(i,0,m)
    76     _for(j,0,n)
    77     {
    78         int tmp;
    79         scanf("%d",&tmp);
    80         if(tmp==1)
    81             mp[i][j] = mp[i][j+1] = mp[i+1][j] = mp[i+1][j+1] = 1;
    82     }
    83     char c;
    84     scanf("%d%d%d%d %c",&st.x,&st.y,&ed.x,&ed.y,&c);
    85     if(c=='N') st.dr = 0;
    86     else if(c=='W') st.dr = 1;
    87     else if(c=='S') st.dr = 2;
    88     else if(c=='E') st.dr = 3;
    89     int rnt = bfs();
    90     if(rnt != INF)
    91         printf("%d\n",bfs());
    92     else
    93         printf("-1\n");
    94     return 0;
    95 }

转载于:https://www.cnblogs.com/Asurudo/p/11241930.html