Maze

You have been blindfolded and deposited someplace in a maze. You have no idea where you are. You do know, however, that the maze is laid out on a grid, and that each grid location is either blocked or free. In fact, you have memorized a map of the maze. Also, your magnetic personality allows you to always sense which direction is north.

In this maze, you have four possible moves: north, south, east, and west. Your task is to find the shortest sequence of moves that will guarantee your escape, regardless of your initial placement in the maze. You have ``escaped" whenever you reach a square on an outside edge of the grid (and if you start there, then you've already escaped). Further moves are irrelevant once you have escaped. If you try to walk into a wall, you will simply stay in the same spot.

You may assume that it is possible to escape from every unblocked position in the maze.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input consists of a positive integer n8, followed by n lines giving the rows of an n by n grid. This grid describes the maze you are trapped in. Written on the screen, north is up. Blocked locations are denoted by the character `O' (that's an uppercase `o'), while unblocked locations are indicated by the character `.'.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output consists of a number of lines, each consisting of one of `north', `south', `east', or `west', indicating the shortest sequence of moves that guarantees escape for any possible unblocked starting position.

If there are multiple possible shortest sequences, any of them will do.

Sample Input 

1

4
OO.O
...O
OO..
O..O

Sample Output 

east
north

---

題目描述：

找到一個最佳化策略，即使被丟到迷宮的任何一地，
也能在最少嘗試步數內逃離迷宮，
假使已經看過這張地圖長什麼樣子。

題目解法：

每一個指令只能走一步，目標所有可能的起始位置按照最少指令可以走到邊界處。
如果其中一種起始位置根據指令撞牆則忽略。

IDA* 
h() : 當前所有未能達到邊界的所有點集到邊界的最短路徑中的最大值
g() : 已知最短路徑

IDA* 保存還沒有走到邊界處的點位置的狀態，因此可以加縮成 64 bits 去保存。

假使收到新的向北指令，則從舊狀態將每個點往北推一格 ... 直到每個點抵達邊界後消失。

可以預處理每一點到邊界的最短距離。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
int n;
char g[10][10];
int dist[10][10];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const char *dir[] = {"north", "west", "south", "east"};
int mxdep, solved;
int path[1024];
unsigned long long state;
void build() {
	state = 0;
	int i, j, k, x, y, tx, ty;
	for(i = 1; i < n-1; i++)
		for(j = 1; j < n-1; j++)
			if(g[i][j] != 'O')
				state |= 1ULL<<(i*8+j);
	queue<int> X, Y;
	memset(dist, 63, sizeof(dist));
	for(i = 0; i < n; i++) {
		if(g[i][0] == '.') {
			dist[i][0] = 0;
			X.push(i), Y.push(0);
		}
		if(g[0][i] == '.') {
			dist[0][i] = 0;
			X.push(0), Y.push(i);
		}
		if(g[i][n-1] == '.') {
			dist[i][n-1] = 0;
			X.push(i), Y.push(n-1);
		}
		if(g[n-1][i] == '.') {
			dist[n-1][i] = 0;
			X.push(n-1), Y.push(i);
		}
	}
	while(!X.empty()) {// bfs
		x = X.front(), X.pop();
		y = Y.front(), Y.pop();
		for(i = 0; i < 4; i++) {
			tx = x+dx[i], ty = y+dy[i];
			if(tx >= 0 && tx < n && ty >= 0 && ty < n) {
				if(g[tx][ty] == 'O') continue;
				if(dist[tx][ty] > dist[x][y]+1) {
					dist[tx][ty] = dist[x][y]+1;
					X.push(tx), Y.push(ty);
				}
			}
		}
	}
}
int H(unsigned long long state) {
	static int i, j;
	int ret = 0;
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			if((state>>(i*8+j))&1) {
				ret = max(ret, dist[i][j]);
			}
		}
	}
	return ret;
}
unsigned long long draw(int dir, unsigned long long state) {
	static int i, j, k, x, y, tx, ty;
	unsigned long long ret = 0;
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			if((state>>(i*8+j))&1) {
				x = i+dx[dir], y = j+dy[dir];
				if(g[x][y] == 'O') {
					ret |= 1ULL<<(i*8+j);
				} else if(x == 0 || y == 0 || x == n-1 || y == n-1) {// clear
				} else {
					ret |= 1ULL<<(x*8+y);
				}
			}
		}
	}
	return ret;
}
int IDA(unsigned long long state, int dep, int hv) {
    if(hv == 0) {
    	for(int i = 0; i < dep; i++)
    		puts(dir[path[i]]);
        solved = dep;
        return dep;
    }
    if(dep+hv > mxdep)  return dep+hv;
    int i;
    int submxdep = 0xfffffff, shv, tmp;
    unsigned long long next;
    for(i = 0; i < 4; i++) {
    	path[dep] = i;
        next = draw(i, state);
        shv = H(next);
        tmp = IDA(next, dep+1, shv);
        if(solved)  return solved;	
        submxdep = min(submxdep, tmp);
    }
    return submxdep;
}
void print(unsigned long long state) {
	int i, j;
	for(i = 0; i < n; i++, puts(""))
		for(j = 0; j < n; j++)
			printf("%d", (state>>(i*8+j))&1);
	puts("");
}
int main() {
	int testcase, cases = 0;
	int i, j, k;
	scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d", &n);
        for(i = 0; i < n; i++)
        	scanf("%s", g[i]);
        build();
        int initH = H(state);
        if(initH == 0) {
        } else {
            solved = 0;
            mxdep = initH;
            while(solved == 0) {
                mxdep = IDA(state, 0, initH);
            }
        }
        if(testcase)
        	puts(""); 
    }
    return 0;
}