ICPC国内予選 2017 G 迷宮を一周

問題

迷路がN*Mのグリッドで与えられる．（'.'が通路，'#'は通行不可）
グリッド上の(0,0)地点をスタートとする．
スタート以外の3隅の宝物を回収してスタート地点に戻ってきたい．
しかし，一度通った通路は通れないとする．
https://storage.googleapis.com/icpcsec/icpc2017-domestic/contest/all_ja.html#section_G

考察

まず，宝物は右回りまたは左回りで回収する必要がある．
右下隅の宝物を最初に取ると，右上隅から左下隅への経路が消えるため．

できるだけ，端に沿ってに移動するのが最適そう（証明は知らないっ！）
下図のように塗って，移動経路があればOKみたいなことをした

各端について（上，右，下，左端の通路）
・端の'.'は通行可能
・”端”の'#'と8近傍で連結している'#'を列挙
・列挙した'#'の8近傍で'.'の通路は通行可能

感想

本番では思いついていたのに，組みきれなかった．
悲しい(´･_･`)

#include <bits/stdc++.h>
using namespace std;

int N,M;
bool dijkstra(vector<string>& maze,char number,int sx,int sy,int gx,int gy){

  priority_queue<pair<int,pair<int,int>>> pq;
  vector<vector<int>> dists(N,vector<int>(M,1e9));
  dists[sy][sx] = 0;
  pq.push(make_pair( 0, make_pair(sx,sy)));  
  vector<int> dx = {0,-1,0,1};
  vector<int> dy = {-1,0,1,0};
  maze[gy][gx] = number;

  while(!pq.empty()){
    pair<int,int> p;
    int cost;
    tie(cost,p) = pq.top();pq.pop();
    int x,y;
    tie(x,y) = p;
    if(x == gx && y == gy)return true;
    for(int i=0;i<4;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(maze[ny][nx] != number)continue;
      int newcost = -cost + 1;
      if(newcost >= dists[ny][nx])continue;
      dists[ny][nx] = newcost;
      pq.push(make_pair( -newcost, make_pair(nx,ny)));
    }
  }
  return false;
}

void fillgrid(vector<string>& maze,char number,int sx,int sy){
  queue<pair<int,int>> q;
  if(number == '1'){
    for(int i=0;i<M;i++){
      if(maze[0][i] == '#')
        q.push(make_pair(i,0));
      else if(maze[0][i] == '.')
        maze[0][i] = number;
    }
  }else if(number == '2'){
    for(int i=0;i<N;i++){
      if(maze[i][M-1] == '#')
        q.push(make_pair(M-1,i));
      else if(maze[i][M-1] == '.')
        maze[i][M-1] = number;
    }
  }else if(number == '3'){
    for(int i=0;i<M;i++){
      if(maze[N-1][i] == '#')
        q.push(make_pair(i,N-1));
      else if(maze[N-1][i] == '.')
        maze[N-1][i] = number;
    }
  }else{
    for(int i=0;i<N;i++){
      if(maze[i][0] == '#')
        q.push(make_pair(0,i));
      else if(maze[i][0] == '.')
        maze[i][0] = number;
    }
  }
  vector<vector<int>> used(N,vector<int>(M,0));
  int dx[] = {0,1,-1,-1,1,0,1,-1};
  int dy[] = {-1,-1,-1,0,0,1,1,1};
  while(!q.empty()){
    int x,y;
    tie(x,y) = q.front();q.pop();
    used[y][x] = 1;
    for(int i=0;i<8;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(used[ny][nx])continue;
      if(maze[ny][nx] == '.'){
        maze[ny][nx] = number;
      }else if(maze[ny][nx] == '#'){
        used[ny][nx] = 1;
        q.push(make_pair(nx,ny));
      }
    }
  }
}

bool solve(){
  cin >> N >> M;
  if(N+M == 0)return false;
  vector<string> maze(N);
  for(int i=0;i<N;i++){
    cin >> maze[i];
  }
  int vsx[] = {0,M-1,M-1,0,0};
  int vsy[] = {0,0,N-1,N-1,0};
  for(int i=0;i<4;i++){
    int sx = vsx[i],sy = vsy[i];
    int gx = vsx[i+1],gy = vsy[i+1];
    fillgrid(maze,'1'+i,sx,sy);
    // for(int i=0;i<N;i++)cerr << maze[i] << endl;

    if(!dijkstra(maze,'1'+i,sx,sy,gx,gy)){
      cout << "NO" << endl;
      return true;
    }
  }
  cout << "YES" << endl;
  return true;
}

int main(void) {
  while(solve()){}
  return 0;
}