Problem 0548 : Reindeer with no sense of direction 方向音痴のトナカイ

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0548&lang=jp

Problem 0548 : Reindeer with no sense of direction
方向音痴のトナカイ

• 問題概要

ある一点から出発して、家を訪問していくのだが、

• 家に配達したときしか方向転換できない。
• 一度配達したところは通れない。

という、めんどくさい条件がある。

• 解法

１０＊１０のグリッドで家が２３個あるので普通にしようとすると状態が多すぎる。
しかし、上の二つの条件から、

• 実際に使用される条件は少ない。

なので、mapに突っ込んで、うしろからDPしてみました。
なぜ、後ろからか。

それは、前からだと、４方向＋どこで降りて配達するかという選択肢があるが、
逆からだと、さいしょにぶつかった、配達済みのところをたどるしかないのでとてもスマートになる。

逆からDP、状態はプレゼントにIDをつけて、「どのプレゼントが配達済みなのか、いまどこにいるのか。」

という状態にしました。

• ソース

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;


class State{
public:
  int x, y;
  bool p[24];
  State(){
    fill(p,p+24, false);
  }
  bool operator<(const State s)const{
    if(x != s.x ){
      return x < s.x;
    }
    if(y != s.y){
      return y < s.y;
    }
    for(int i=0; i<24; i++){
      if(p[i] != s.p[i]){
	return p[i] < s.p[i];
      }
    }
    return false;
  }
}; 


main(){

  int h, w;
  
  while(cin >> w >> h){
    if(w+h == 0){
      break;
    }
    int m[h][w];
    int cnt = 1, sx, sy;
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
	int tmp;
	cin >> tmp;
	if(tmp == 1){
	  m[i][j] = cnt;
	  cnt++;
	}
	else if(tmp == 2){
	  m[i][j] = 0;
	  sy = i;
	  sx = j;
	}
	else m[i][j] = -1;
      }
    }
    State s;
    s.x = sx;
    s.y = sy;
    map<State, int> nowmap;
    nowmap[s] = 1;
    int tx[] = {0, 0, -1, 1};
    int ty[] = {-1, 1, 0, 0};
    for(int i=0; i<cnt; i++){
      map<State, int> nextmap;
      for(map<State,int>::iterator it = nowmap.begin(); it != nowmap.end(); it++){
	for(int j=0; j<4; j++){
	  int nx = (*it).first.x, ny = (*it).first.y;
	  while(1){ 
	    nx += tx[j];
	    ny += ty[j];
	    if(nx < 0 || ny < 0 || nx >= w || ny >= h){
	      break;
	    }
	    if(m[ny][nx] == -1 || (i != cnt-1 && m[ny][nx] == 0)){
	      continue;
	    }
	    if((m[ny][nx] == 0 && i == cnt-1) || m[ny][nx] != 0){
	      State now = (*it).first;
	      int p = m[ny][nx];
	      if(now.p[p]){
		continue;
	      }
	      now.p[p] = true;
	      now.x = nx;
	      now.y = ny;
	      nextmap[now] += (*it).second;
	      break;
	    }
	  }
	}
      }
      nowmap = nextmap;
    }
    State end;
    end.x = sx;
    end.y = sy;
    for(int i=0; i<cnt; i++){
      end.p[i] = true;
    }
    cout << nowmap[end] << endl;
  }
}