1 solutions

  • 0
    @ 2025-11-5 18:04:11

    C++ :

    #include <algorithm>
    #include <cassert>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <deque>
    #include <queue>
    #include <vector>
    using namespace std;
     
    #define FR(i,a,b) for(int i=(a);i<(b);++i)
    #define FOR(i,n) FR(i,0,n)
    #define CLR(x,a) memset(x,a,sizeof(x))
    #define setmax(a,b) a = max(a,b)
    #define PB push_back
    #define BEND(v) (v).begin(),(v).end()
    #define MP make_pair
    #define A first
    #define B second
     
    int R,C;
    int i1,jj1,i2,j2;
    bool mark[20][20][4][1601];
    int dist[20][20][4][1601];
    bool pass[20][20][4];
    int dr[] = { -1, 0, 1, 0 },
        dc[] = { 0, 1, 0, -1 };
    deque<pair<pair<int,int>, pair<int,int> > > q;
    void enq(int d, int r, int c, int rot, int rem) {
      assert(rem <= 1600);
      if (rem < 0) return;
      if (mark[r][c][rot][rem]) return;
      q.PB(MP(MP(r,c),MP(rot,rem)));
      mark[r][c][rot][rem] = 1;
      dist[r][c][rot][rem] = d;
    }
    void doit() {
      scanf("%d%d",&R,&C);
      if (R==0) exit(0);
     
      scanf("%d%d%d%d",&i1,&jj1,&i2,&j2);
      --i1;--jj1;--i2;--j2;
     
      CLR(pass,0);
      FOR(r,R) {
        FOR(c,C) {
          char buf[256];
          scanf("%s",buf);
     
          if (buf[0] == 'x') continue;
     
          for (char *p = buf; *p; ++p) {
        pass[r][c][
          *p=='N' ? 0 :
          *p=='E' ? 1 :
          *p=='S' ? 2 :
                3] = 1;
          }
        }
      }
     
      CLR(mark,0);
      q.clear();
      q.PB(MP(MP(i1,jj1), MP(0,0)));
      mark[i1][jj1][0][0] = 1;
      dist[i1][jj1][0][0] = 0;
     
      int ans = -1;
      while (q.size()) {
        int r = q.front().A.A,
        c = q.front().A.B,
        rot = q.front().B.A,
        rem = q.front().B.B,
        d = dist[r][c][rot][rem];
        q.pop_front();
     
        if (r == i2 && c == j2) {
          ans = d;
          break;
        }
     
        for (int drot = -1; drot <= 1; ++drot) {
          int rotp = (rot+drot+4)%4;
          int remp = rem + (drot==0);
     
          enq(d+1, r, c, rotp, remp);
     
          FOR(k,4) {
        int r2 = r + dr[k], c2 = c + dc[k];
        if (r2<0 || r2>=R || c2<0 || c2>=C) continue;
        int kp = (k+rotp)%4;
        if (!pass[r][c][kp]) continue;
         
        for (int drot2 = -1; drot2 <= 2; ++drot2) {
          if (abs(drot2) > remp) continue;
          int rot2 = (drot2+4)%4,
              rem2 = remp - abs(drot2);
          if (!pass[r2][c2][(k+rot2+2)%4]) continue;
     
          enq(d+1, r2, c2, rot2, rem2);
        }
          }
        }
      }
     
      printf("%d\n",ans);
    }
     
    const int MULTICASE = 1;
    int main() {
      do {
        doit();
      } while (MULTICASE);
    }
    
    • 1

    Information

    ID
    18753
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By