AOJ 2017 : Karakuri Doll - 土下座しながら探索中

問題リンク：Karakuri Doll | Aizu Online Judge

問題概要：
H*Wのグラフが与えられる
カラクリ人形は壁にぶつかるまでまっすぐに進む
壁にぶつかった後、右か左にまがることができる
キッチンKからマスターのいる場所Mに行きそれまでの順番と方向を逆にしてキッチンKに戻ることが可能か？
それが不可能なとき、せめてキッチンへたどり着くことはできるか
それすらできないか判定せよ

使用した言語：C++

解法：
KからMまでをdfsで探索した
KからMまでを探索する過程で同時にMからKまでのルートも探索する

まずKに２つ人形をおき、１つは素直に（前を向いて）KからMまで向かうもの
もう一つはKからMまで後ろ向きですすむものとする
素直にKからMまで向かうものはなにも気にせず探索するだけでよい
KからMに後ろ向きで向かう人形は方向転換した後必ず目の前は壁でなければならない（方向転換していない時、つまり後ろ向きにすすんでいる時は前に壁がなくてもよい）
でないと前向きで移動させたときに壁にぶつかっていないのにまがったことになるからである
手順としては、
1.目の前が壁か判定する
2.もし目の前が壁なら後ろ向きで背中が壁にぶつかるまで一歩一歩さがっていく
3.一歩さがるごとに左右に方向を変えた場合もためす
左右に方向を変える際には、素直にKからMまで進んでいる人形と逆の向きを選ばなくてはならない
素直にすすんでいる人形が右を向いたら同じタイミングでもう一方の人形は左をむく
同じタイミングで逆を向いて両方の人形が条件を満たす状態になったということはカラクリ人形はKからMへ、その逆も逆順番でいけるということになる
ここでいう条件を満たす状態とは2つの人形がMに存在し、なおかつ逆向きできた人形は壁のない方向を向いていることである

例えば、
前向きで進む人形が　右右左　という順番で曲がることでゴールしたとき
それを折り返すために今度は人形は　左左右　とまがらなければならない
前向きに進む人形と左右反対で動かすことで
前向き人形 : 右右左
後向き人形 : 左左右
となりこの順番で動かしたあと条件を満たす状態であればすでにMからKへいけるかどうかの判定も終わっていることになる

ここからは問題のアルゴリズムとは関係ないのだが、
最初にこの問題をみた時これといった解法がおもいつかなかったのでとりあえずKからMまで移動させて到達したら実際その逆でうまくいくか判定させたが案の定重すぎてサンプルすら通らなかった
その後もdfsからbfsに書き換えたり(結果むしろ遅くなった)dequeをいじくったり反復深化したら・・・？マンハッタン距離は？などなど考えたがどれもぐるぐる回るパターンに撃墜されてしまうのでどうしようもなかった
12時間後、プログラミング始める前は真夜中だったのに気がつけば暴れん坊将軍がやっていたのでそれを見ていたら悪事をはたらいたことがばれた悪代官のいさぎの悪さをみて、自分は潔く諦めようと思いJAGの解説を読んでみたが、理解できなかった
師匠に意見をもとめるも解いたのが数年前なので忘れたという前代未聞の大ピンチに陥ったが、最近のAOJは解いた人で公開している人のコードをみれるのでそのうちの一人のとても綺麗なコードをかいている方のコードをみながらJAGの解説と照らし合わせなんとか理解できた
そして今にいたる
今日も気がつけば朝のニュースがはじまっている
明後日は立命館の合宿にも参加するので疲れをとらなくては
寝ましょう

コード：

#include<iostream>
#include<deque>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<sstream>
#include<bitset>
#include<cstring>
#include<climits>
#include<cassert>
#define F first
#define S second
#define rep(i,n) for(int i=0;i<n;i++)
#define T 0
#define R 1
#define B 2
#define L 3
#define PesIns(a,b,c,d) Pes(PP(P(a.x,a.y),P(b.x,b.y)),P(c,d))
using namespace std;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<VVB> VVVB;
typedef vector<VC> VVC;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef pair<PP,P> Pes;


struct Point
{
  int x,y;
  Point(int x = -1,int y = -1):x(x),y(y){}
  bool operator == (const Point& p)const
  {
    return (x == p.x && y == p.y);
  }
  friend ostream& operator << (ostream& os,const Point& p);
};

ostream& operator << (ostream& os,const Point& p)
{
  os << "(" << p.x << "," << p.y << ")";
}



int H,W;
char G[17][65];
Point K,M;
VVVB visited;
map<Pes,bool> exist;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int add[] = {1,3};
bool M_ok,K_ok;
int est;

string debug(int d)
{
  if(d == 0)
    return "T";

  if(d == 1)
    return "R";

  if(d == 2)
    return "B";

  if(d == 3)
    return "L";

  return "X";
}

void dfs(Point p1,Point p2,int dir1,int dir2,bool f)
{
  
  if(K_ok)
    return;

  if(!f && M_ok)
    return;

  Pes pes = PesIns(p1,p2,dir1,dir2);
  if(exist[pes])
  return;
  exist[pes] = true;

  if(f && G[p2.y+dy[dir2]][p2.x+dx[dir2]] != '#')
      return;


  while(G[p1.y+dy[dir1]][p1.x+dx[dir1]] != '#')
    p1.x += dx[dir1],p1.y += dy[dir1];


  if(f && p1 == M && p1 == p2 && G[M.y+dy[dir2]][M.x+dx[dir2]] == '.')
    {
      K_ok = true;
      return;
    }  
  else if(!f && p1 == M)
    {
      M_ok = true;
      return;
    }

  
  if(f)
    {
      while(G[p2.y][p2.x] != '#')
	{    
	  rep(i,2)
	    {
	      dfs(p1,p2,(dir1+add[i])%4,(dir2+add[i])%4,f);	
	      
	      if(K_ok)
		return;
	    }
	  
	  p2.x += dx[(dir2+2)%4],p2.y += dy[(dir2+2)%4];
	}
      p2.x += dx[dir2],p2.y += dy[dir2];
    }
  else 
    {
      rep(i,2)
	{
	  dfs(p1,p2,(dir1+add[i])%4,dir2,f);
	  if(M_ok)
	    return;
	}
    }
  if(p1 == M && p1 == p2 && G[M.y+dy[dir2]][M.x+dx[dir2]] == '.')
    {
    
      K_ok = true;
      return;
    }
  else if(!f && p1 == M)
    {
      M_ok = true;
      return;
    }
 
}



int main()
{

  while(cin >> W >> H,H|W)
    {
  
      M_ok = K_ok = false;
      exist.clear();
      visited.clear();
      visited.resize(4);
      rep(i,4)
	visited[i].resize(H);

  
      rep(i,H)
	{
	  rep(j,4)
	    visited[j][i].resize(W);
	  string line;
	  cin >> line;
	  rep(j,W)
	    {
	      rep(k,4)
		visited[k][i][j] = false;
	      G[i][j] = line[j];
	
	      if(G[i][j] == 'K')
		K = Point(j,i);
	      else if(G[i][j] == 'M')
		M = Point(j,i);
	    }
	}

      int inidir = -1;
      rep(i,4)
	if(G[K.y+dy[i]][K.x+dx[i]] == '.')
	  inidir = i;
      dfs(K,Point(-1,-1),inidir,-1,false);	 
      rep(i,4)
	{
	  dfs(K,K,inidir,i,true);
	  
	  if(K_ok)
	    break;
	}
	if(K_ok)
	cout << "He can accomplish his mission." << endl;
	else if(M_ok)
	  cout << "He cannot return to the kitchen." << endl;
	else
	  cout << "He cannot bring tea to his master." << endl;
    }
  return 0;
}