AOJ 2640 Prowler - たこし++の備忘録

問題

問題概要

$N*M$ の迷路を右手を離さずにスタートからゴールまでいくとき、ゴールできるときは通った異なるマスの数の最小値を、ゴールできない時は-1を出力する。
$N \le 50$ $M \le 50$
解法

ゴールできるときはルートが一通りに確定するので、通ってきたマスの数を重複しないように数えたものを出力すればいい。
あとは頑張って実装する。
コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define LL unsigned long long
#define PI acos(-1)
#define INF 1e8
#define EPS 1e-9

using namespace std;

#define MAX_N 55
#define MAX_M 55

int N, M;
char maze[MAX_N][MAX_M];
int sx, sy;
int gx, gy;
int sd;

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

int turnx[] = {0,1,1,1,0,-1,-1,-1};
int turny[] = {-1,-1,0,1,1,1,0,-1};

bool used[MAX_N][MAX_M];

void Init(){
  memset(maze, '#', sizeof(maze));
}

void Input(){

  cin >> N >> M;
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= M; j++){
      cin >> maze[i][j];
      if(maze[i][j] != '.' && maze[i][j] != '#'){
	if(maze[i][j] == 'G'){
	  gx = j;
	  gy = i;
	}
	else{
	  sx = j;
	sy = i;
	if(maze[i][j] == '^')
	  sd = 0;
	else if(maze[i][j] == '>')
	  sd = 1;
	else if(maze[i][j] == 'v')
	  sd = 2;
	else if(maze[i][j] == '<')
	  sd = 3;
	}
      }
    }
  }

}

typedef pair<int, int> II;

class cProwler{
public:
  int x, y; //現在地
  int dir; //向いてる向き
  int hand_dir; //手をついてる座標

  cProwler(){
    x = sx; y = sy;
    dir = sd;
    used[sy][sx] = true;
  }

  //初期のスタート状態を列挙したものを返す
  vector<cProwler> GetStartStatus(){
    
    vector<cProwler> ret;
    
    x = sx;
    y = sy;
    dir = sd;

    for(int i = 0; i < 8; i++){
      if(maze[y+turny[i]][x+turnx[i]] != '#')
	continue;
      hand_dir = i;
      if(CheckTouchWall(dir)){
	cProwler p;
	CopyClass(p);
	ret.push_back(p);
      }
    }

    return ret;
    
  }

  void CopyClass(cProwler& c){
    c.x = x; c.y = y;
    c.hand_dir = hand_dir;
    c.dir = dir;
  }

  //右手の座標を変える
  vector<cProwler> GetChangeHand(){
    
    vector<cProwler> ret;

    if(dir != 3){
      int s = dir * 2;
      int e = (dir+2)*2;
      for(int i = hand_dir; i >= s; i--){
	int nx = x + turnx[i];
	int ny = y + turny[i];
	if(maze[ny][nx] != '#' && i%2 == 0)
	  break;
	if(maze[ny][nx] != '#')
	  continue;
	cProwler p;
	CopyClass(p);
	p.hand_dir = i;
	ret.push_back(p);
      }
      for(int i = hand_dir+1; i <= e; i++){
	int nx = x + turnx[i];
	int ny = y + turny[i];
	if(maze[ny][nx] != '#' && i%2 == 0)
	  break;
	if(maze[ny][nx] != '#')
	  continue;
	cProwler p;
	CopyClass(p);
	p.hand_dir = i;
	ret.push_back(p);
      }
    }
    else{
      int s = 6;
      int e = 9;
      int sHandDir = hand_dir;
      if(sHandDir < 6)
	sHandDir += 8;
      for(int i = sHandDir; i >= s; i--){
	int nx = x + turnx[i%8];
	int ny = y + turny[i%8];
	if(maze[ny][nx] != '#' && i%2 == 0)
	  break;
	if(maze[ny][nx] != '#')
	  continue;
	cProwler p;
	CopyClass(p);
	p.hand_dir = i%8;
	ret.push_back(p);
      }
      for(int i = sHandDir+1; i <= e; i++){
	int nx = x + turnx[i%8];
	int ny = y + turny[i%8];
	if(maze[ny][nx] != '#' && i%2 == 0)
	  break;
	if(maze[ny][nx] != '#')
	  continue;
	cProwler p;
	CopyClass(p);
	p.hand_dir = i%8;
	ret.push_back(p);
      }
    }

    return ret;

  }

  //右手が壁から離れていないか(今向いている向き)
  bool CheckTouchWall(int tmpDir){
    int s = tmpDir*2;
    for(int i = 0; i < 4; i++){
      int ts = (s+i)%8;
      if(hand_dir == ts)
	return true;
    }
    return false;
  }

  //左を向くことができるか
  bool CheckTurnLeft(){
    int tmpDir = (dir+3) % 4;
    return CheckTouchWall(tmpDir);
  }

  //右を向くことができるか
  bool CheckTurnRight(){
    int tmpDir = (dir+1) % 4;
    return CheckTouchWall(tmpDir);
  }

  //左を向く
  bool TurnLeft(){
    if(!CheckTurnLeft())
      return false;
    dir = (dir+3) % 4;;
    return true;
  }

  //右を向く
  bool TurnRight(){
    if(!CheckTurnRight())
      return false;
    dir = (dir+1)%4;
    return true;
  }

  //今向いている方向に歩けるか
  bool CheckMove(){
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if(maze[ny][nx] != '#' && ((dir*2+1 <= hand_dir && hand_dir <= dir*2+2) || 
			       (dir == 3 && (hand_dir == 7 || hand_dir == 0))))
      return true;
    else
      return false;
  }

  //まっすぐ進む
  bool GetMove(){
    if(!CheckMove())
      return false;
    x += dx[dir];
    y += dy[dir];
    hand_dir = (hand_dir+1) % 8;
    used[y][x] = true;
    return true;
  }

  //反対方向を向けるか
  bool CheckReturn(){

    //cerr << "Return Ivent" << endl;

    int s = (dir*2 + 8 - 2) % 8;
    for(int i = 0; i < 3; i++){
      if(maze[y+turny[s]][x+turnx[s]] != '#'){
	//cerr << i << " false" << endl;
	return false;
      }
      s = (s+2) % 8;
    }

    //cerr << "true" << endl;
    return true;

  }

  //反対方向を向く
  bool GetReturn(){
    
    if(!CheckReturn())
      return false;
    dir = (dir+2)%4;
    hand_dir = (dir+1)*2 % 8;
    return true;    

  }

  void DebugPirnt(){
    cerr << "***" << endl;
    fprintf(stderr, "pos(%d, %d), dir:%d, hand:(%d, %d)\n", x, y, dir, x+turnx[hand_dir], y+turny[hand_dir]);
    cerr << "***" << endl;
  }

};

class cCheckMaze{
public:
  int dp[MAX_N][MAX_M][10];

  cCheckMaze(){
    memset(dp, -1, sizeof(dp));
    memset(used, 0, sizeof(used));
  }

  int CalcCount(){

    int ret = 0;
    for(int i = 0; i <= N+2; i++){
      for(int j = 0; j <= M+2; j++){
	if(used[i][j])
	  ret++;
      }
    }

    return ret;

  }

  void Solve(){
    
    cProwler tmpProwler;
    vector<cProwler> pList = tmpProwler.GetStartStatus();
    queue<cProwler> que;
    for(int i = 0; i < pList.size(); i++){
      tmpProwler = pList[i];
      //tmpProwler.DebugPirnt();
      que.push(tmpProwler);
    }

    while(que.size()){
      
      tmpProwler = que.front();
      que.pop();

      //tmpProwler.DebugPirnt();
      
      if(tmpProwler.x == gx && tmpProwler.y == gy){
	cout << CalcCount() << endl;
	return;
      }

      if(dp[tmpProwler.y][tmpProwler.x][tmpProwler.hand_dir] >= 0)
	continue;

      dp[tmpProwler.y][tmpProwler.x][tmpProwler.hand_dir] = 0;
      
      //まっすぐむいて進む
      if(tmpProwler.CheckMove()){
	//cerr << "Straight" << endl;
	cProwler nextProwler = tmpProwler;
	//まっすぐ進む
	nextProwler.GetMove();
	//手を変える
	pList.clear();
	pList = nextProwler.GetChangeHand();
	for(int i = 0; i < pList.size(); i++){
	  nextProwler = pList[i];
	  if(dp[nextProwler.y][nextProwler.x][nextProwler.hand_dir] < 0){
	    que.push(nextProwler);
	  }
	}
      }

      //左を向いて進む
      if(tmpProwler.CheckTurnLeft()){
	cProwler nextProwler = tmpProwler;
	//左を向く
	nextProwler.TurnLeft();
	//cerr << "Turn Left" << endl;
	if(nextProwler.CheckMove()){
	  //cerr << "Straight" << endl;
	  nextProwler.GetMove();
	  //手を変える
	  pList.clear();
	  pList = nextProwler.GetChangeHand();
	  for(int i = 0; i < pList.size(); i++){
	    nextProwler = pList[i];
	    if(dp[nextProwler.y][nextProwler.x][nextProwler.hand_dir] < 0){
	      que.push(nextProwler);
	    }
	  }
	}
      }

      //右を向いて進む
      if(tmpProwler.CheckTurnRight()){
	cProwler nextProwler = tmpProwler;
	//右を向く
	nextProwler.TurnRight();
	//cerr << "Turn Right" << endl;
	if(nextProwler.CheckMove()){
	  //cerr << "Straight" << endl;
	  nextProwler.GetMove();
	  //手を変える
	  pList.clear();
	  pList = nextProwler.GetChangeHand();
	  for(int i = 0; i < pList.size(); i++){
	    nextProwler = pList[i];
	    if(dp[nextProwler.y][nextProwler.x][nextProwler.hand_dir] < 0){
	      que.push(nextProwler);
	    }
	  }
	}
      }

      //引き返す
      if(tmpProwler.CheckReturn()){
	cProwler nextProwler = tmpProwler;
	nextProwler.GetReturn();
	//cerr << "Return" << endl;
	if(nextProwler.CheckMove()){
	  //cerr << "Straight" << endl;
	  nextProwler.GetMove();
	  //手を変える
	  pList.clear();
	  pList = nextProwler.GetChangeHand();
	  for(int i = 0; i < pList.size(); i++){
	    nextProwler = pList[i];
	    if(dp[nextProwler.y][nextProwler.x][nextProwler.hand_dir] < 0){
	      que.push(nextProwler);
	    }
	  }
	}
      }

    }

    cout << -1 << endl;

    return;

  }

};

int main(){

  Init();
  Input();

  cCheckMaze CheckMaze;

  CheckMaze.Solve();

  return 0;

}