AOJ 1025 : Building Water Ways - 土下座しながら探索中

問題リンク : Building Water Ways | Aizu Online Judge

問題概要 :
日本語なので略

解法 :
枝刈り＋バックトラック

手順 :
* ０から順に水源に番号を付ける
* ０から順に水源を伸ばしていく ( 0 を伸ばし終わったら 1 へ...といった感じで )
* 全ての町に水がとどいたら最小値を更新して次へ

20sec から減らない

> 今見ているマスが'*'と隣接しているならそこに移動する

その他の3方向は見なくても良い ( 他に'*'があったとしてもそれは invalid な状態なので見なくて良い )
もし'*'に移動しないとすると、もうその'*'をとれない
( 他の水源がそれをとると水源同士がつながってしまい制約に反するし、
後で自分でとったとしてもループができてしまい制約に反する )

これを付けたら 8sec まで落ちた
8sec から減らない

> 中途半端なマスで水源を変えない

水源に0から順に番号を割り振って0をどのように伸ばすか、
1をどのように伸ばすか...とやっていくのだが、
水源を次のものに変更するタイミングは今いるマスが'*'か'P'の時だけ
それ以外のマスで変更するなら、そのマスは意味がないので訪れる必要はない

最初IDA*で書いたがTLEがとれないので諦めた
ヒューリスティック値の計算に最大8回とはいえ時間がかかるのでダメっぽい
メモリに余裕がない〜などと言っている余裕はない
時間に余裕がないなら使えない
ただあの時は2つ目の枝刈りをしていなかったのでそれを付けたら通るのかなあ

テストケースも載せておく

10 10
##########
#P.....*.#
#...P....#
#.*...P.*#
#...P....#
#.*...P..#
#...P...*#
#......P.#
#.**.*..P#
##########
3 8
########
#P....*#
########
10 10
##########
#P.......#
#..#*....#
#..#*.#.*#
#.....#*.#
#*.......#
#..##....#
#...#.P..#
#P......P#
##########
3 3
###
#P#
###
10 10
##########
#P..*.P.P#
#....P.P.#
#........#
#......**#
#*.......#
#........#
#.......*#
#*..*...*#
##########
8 6
######
#*.*.#
##.#.#
##.#.#
##.#.#
##.#.#
#P..P#
######
10 10
##########
#P......*#
#........#
#..*.*.*.#
#..#######
#..*.*.*.#
#...P....#
#.P...P..#
#.......*#
##########
10 10
##########
#........#
#..P.....#
#........#
#..***##.#
#..*.*...#
#.#*.*...#
#..#.....#
#........#
##########
10 10
##########
#P.*.....#
####P#####
#..#....P#
#.#.....##
#.#.#...*#
#......#.#
#.###..#.#
#*....#.*#
##########
10 10
##########
#.......P#
#........#
#.......P#
#.###....#
#*#*#**..#
##..#.*..#
#..*#*...#
#........#
##########
10 10
##########
#...P.P.P#
#........#
#.*#*..#.#
#.#*#.*..#
#*.....#.#
##*#*#.*##
#........#
#P..P....#
##########
0 0

10 10
##########
#*#*#..*.#
#.#......#
#.....#*##
#P.P...#P#
#........#
#P.*P....#
#.*#....*#
#.#*....P#
##########
0 0

コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define _3_ 1
 
using namespace std;
 
typedef unsigned long long ull;
typedef pair<int,int> ii;
 
struct Point { int x,y; };
 
const int IINF = INT_MAX;
const char PATH = '$';
 
int h,w,s_size,c_size,bitIndex[12][12];
char c[12][12];
Point source[12],city[12],path[12];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int mini,blocks;
int bc[1<<9];
 
void dfs(int sp,int bitmask,int prev,int step,int depth){
 
  if( step+(c_size-bc[bitmask]) >= mini ) return;
   
  if( sp >= s_size ) return;
 
  if( bitmask == ((1<<c_size)-1) ) { mini = step; return; }
 
  bool next = 1;
  rep(dir,4){
    if( prev != -1 && ( prev + 2 ) % 4 == dir ) continue;
    int nx = path[sp].x + dx[dir], ny = path[sp].y + dy[dir];
 
    if( c[ny][nx] == 'P' || c[ny][nx] == '#' || c[ny][nx] == PATH ) continue;
 
    bool success = true;
    int cnt = 0;
    rep(i,4){
      int nx2 = nx + dx[i], ny2 = ny + dy[i];
      if( c[ny2][nx2] == PATH || c[ny2][nx2] == 'P' ) ++cnt;
    }
    if( cnt != 1 ) success = false;
    if( !success ) continue;
     
    Point pp = path[sp];
    char pc = c[ny][nx];
    int nbitmask = bitmask;
    bool fin = false;
    if( c[ny][nx] == '*' ) nbitmask |= (1<<bitIndex[ny][nx]), fin = true;
 
    path[sp] = (Point){nx,ny};
    c[ny][nx] = PATH;
 
    next = 0;
    dfs(sp,nbitmask,dir,step+1,depth+1);
    if( fin )dfs(sp+1,nbitmask,-1,step+1,0);
 
    path[sp] = pp;
    c[ny][nx] = pc;
 
     if( fin ) return; 
 
  }
 
  if( depth == 0 )  dfs(sp+1,bitmask,-1,step,0);  
} 
 
int compute(){
  mini = h*w-s_size - blocks;
  dfs(0,0,-1,0,0);
  return mini;
}
 
 
 
int main(){
  rep(i,(1<<9)) bc[i] = __builtin_popcount(i);
  while( scanf(" %d %d",&h,&w), h|w ){
    s_size = c_size = 0;
    blocks = 0;
    rep(i,h) rep(j,w) {
      scanf(" %c",&c[i][j]);
      if( c[i][j] == 'P' ) { source[s_size] = path[s_size] = (Point){j,i}; s_size++; }
      if( c[i][j] == '*' ) { city[c_size]   = (Point){j,i}; bitIndex[i][j] = c_size++; }
      if( c[i][j] == '#' ) ++blocks;
    }
    printf("%d\n",compute());
    //print_field(); puts("");
  }
  return 0;
}