Submission #306475

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int dy[5] = {0,1,0,-1,0};
const int dx[5] = {1,0,-1,0,0};

int main() {
  int H, W; scanf("%d%d", &H, &W);
  static char maze[60][60];
  for(int y = 0; y < H; ++y) {
    maze[y][0] = '#';
    scanf(" %s", maze[y+1]+1);
    maze[y][W+1] = '#';
  }
  fill(maze[0],maze[0]+(W+2), '#');
  fill(maze[H+1],maze[H+1]+(W+2), '#');
  pair<int,int> start, goalA, goalB;
  for(int y = 0; y < H+2; ++y) {
    for(int x = 0; x < W+2; ++x) {
      if(maze[y][x]=='S') start=make_pair(y,x);
      if(maze[y][x]=='A') goalA=make_pair(y,x);
      if(maze[y][x]=='B') goalB=make_pair(y,x);
    }
  }
  static int levels[60][60];
  for(int y = 0; y < H+2; ++y) fill(levels[y],levels[y]+(W+2),-1);
  static pair<int,int> q[60*60];
  int qs = 0, qe = 0;
  levels[start.first][start.second] = 0;
  q[qe++] = start;
  while(qs<qe) {
    pair<int,int> p = q[qs++];
    int l = levels[p.first][p.second];
    for(int dir = 0; dir < 4; ++dir) {
      int y = p.first+dy[dir];
      int x = p.second+dx[dir];
      if(maze[y][x] != '#' && levels[y][x]==-1) {
        levels[y][x] = l+1;
        q[qe++] = make_pair(y,x);
      }
    }
  }

  static bool b2vis[60][60][60][60];
  static char parent[60][60][60][60];
  memset(b2vis,0,sizeof(b2vis));
  queue<pair<pair<int,int>,pair<int,int>>> b2q;
  b2vis[start.first][start.second][start.first][start.second] = true;
  b2q.push(make_pair(start,start));
  while(!b2q.empty()) {
    pair<pair<int,int>,pair<int,int>> p = b2q.front();
    b2q.pop();
    int l = max(levels[p.first.first][p.first.second],
                levels[p.second.first][p.second.second]);
    // fprintf(stderr, "(%d, %d), (%d, %d), level=%d\n",
    //     p.first.first,
    //     p.first.second,
    //     p.second.first,
    //     p.second.second, l);
    bool isGoalA = p.first == goalA;
    bool isGoalB = p.second == goalB;
    int dirAmin = isGoalA ? 4 : 0;
    int dirAmax = isGoalA ? 5 : 4;
    int dirBmin = isGoalB ? 4 : 0;
    int dirBmax = isGoalB ? 5 : 4;
    for(int dirA = dirAmin; dirA < dirAmax; ++dirA) {
      for(int dirB = dirBmin; dirB < dirBmax; ++dirB) {
        int y1 = p.first.first+dy[dirA];
        int x1 = p.first.second+dx[dirA];
        int y2 = p.second.first+dy[dirB];
        int x2 = p.second.second+dx[dirB];
        if(!isGoalA && levels[y1][x1] != l+1) continue;
        if(!isGoalB && levels[y2][x2] != l+1) continue;
        // if(x1==x2 && y1==y2)
        //   fprintf(stderr, "(%d,%d) = (%d,%d)\n", x1, y1, x2, y2);
        if(y1==y2 && x1==x2) continue;
        if(b2vis[y1][x1][y2][x2]) continue;
        // if(y1==7&&x1==5&&y2==8&&x2==4) {
        //   fprintf(stderr, "(%d,%d),(%d,%d)->, dirA=%d, dirB=%d\n",
        //       p.first.first,p.first.second,
        //       p.second.first,p.second.second,dirA,dirB);
        // }
        b2vis[y1][x1][y2][x2] = true;
        parent[y1][x1][y2][x2] = (dirA<<3)|dirB;
        b2q.push(make_pair(make_pair(y1,x1),make_pair(y2,x2)));
      }
    }
  }
  // printf("%s\n", b2vis[goalA.first][goalA.second][goalB.first][goalB.second] ?
  //     "YES" : "NO");
  if(b2vis[goalA.first][goalA.second][goalB.first][goalB.second]) {
    pair<pair<int,int>,pair<int,int>> c(goalA,goalB);
    while(c.first != start) {
      // fprintf(stderr, "(%d,%d), (%d,%d)\n",
      //     c.first.first, c.first.second,
      //     c.second.first, c.second.second);
      // if(!b2vis[c.first.first][c.first.second][c.second.first][c.second.second]) {
      //   fprintf(stderr, "something is weird\n");
      //   break;
      // }
      if(c.first != goalA) maze[c.first.first][c.first.second] = 'a';
      if(c.second != goalB) maze[c.second.first][c.second.second] = 'b';
      int parlink = parent[c.first.first][c.first.second]
                          [c.second.first][c.second.second];
      int dirA = parlink>>3;
      int dirB = parlink&7;
      c = make_pair(
          make_pair(c.first.first-dy[dirA],c.first.second-dx[dirA]),
          make_pair(c.second.first-dy[dirB],c.second.second-dx[dirB]));
    }
    for(int y = 1; y < H+1; ++y) {
      for(int x = 1; x < W+1; ++x) {
        printf("%c", maze[y][x]);
      }
      printf("\n");
    }
  } else {
    printf("NA\n");
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:11:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int H, W; scanf("%d%d", &H, &W);
                                  ^
./Main.cpp:15:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", maze[y+1]+1);
                              ^

Judge Result