题目

1426 - Blind Escape

PDF (English)

Statistics

Forum

Illidan Stormage, the blind Warcraft hero is thrown to a maze for punishment. Being a blind hero, he cannot see anything but he can sense which direction is
north. He memorized the map of the maze when he was a child. But he doesn't know his exact location now.

Assume that the maze is laid out on a grid, and each grid location is either blocked or free. He has four possible moves:
North, South, East and West. He wants to find the shortest sequence of moves that will guarantee his escape (his initial location can be any free cell in the grid). He is said to be escaped if he is outside the maze and once
he is out of the maze, further moves are irrelevant. And of course if he tries to walk into a wall, he will simply stay in the same spot.

As he cannot see anything, for any move, he will only stop if he bumps into a wall or he is out of the maze. Now your task is to help him by finding the shortest sequence of moves.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing two integers M and
N (1 ≤ M, N ≤ 12) denoting the number of rows and columns of the grid respectively. Each of the next
M lines contains N characters (either '.' or
'#') denoting the maze. '.' means free location and '#' means a wall. Assume that there is at least one free location in the grid.

Output

For each case, print the case number first. If it's impossible to do so, print
"Impossible". Otherwise, print the shortest possible sequence of moves that guarantees his escape. Show the sequence by the first letters of the moves. As there can be many solutions, print the one that comes lexicographically earliest. See
the samples for details.

题解

整个题目意思不难理解，盲人走迷宫，给他一个万能的指令，让他不管在迷宫的哪个地方都能按照这个命令走出来，如果不行，那就输出“Impossible”。

我是先对每一个可能的点进行深搜，看看是否能出来，当然要剪枝否则时间开销会很大。对于任意一个点都能出来迷宫，再进行广搜，把解输出来。具体的看代码吧。

代码示例

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

typedef pair<int, int> pnt;
typedef vector<pnt> vp;
const int D = 4, N = 16;
const int  di[D] = { 0 , -1 ,  1 ,  0 };
const int  dj[D] = { 1 ,  0 ,  0 , -1 };
const char dc[D] = {'E', 'N', 'S', 'W'};

vp s, u, v;
queue<vp> q;
map<vp, string> mov;

char a[N][N];
bool vis[N][N];
int r, c, nxti[N][N][4], nxtj[N][N][4];


void min_represent(vp& v){
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
}

bool in_bounds(int i,int j){
    return 1<=i && i<=r && 1<=j && j<=c;
}

void Read(){
    scanf("%d %d",&r,&c);
    for (int i=1;i<=r;i++)
		scanf("%s",a[i]+1);
	return;
}

void Init(){
    s.clear();
    for (int i=1;i<=r;i++)
	for (int j=1;j<=c;j++)
		for (int d=0;d<D;d++)
			if (a[i][j] == '.'){
				s.push_back(pnt(i,j));
				int& ni=nxti[i][j][d];
				int& nj=nxtj[i][j][d];
				for (ni=i+di[d],nj=j+dj[d];in_bounds(ni,nj) && a[ni][nj]=='.';ni+=di[d],nj+=dj[d]){}
				if (in_bounds(ni,nj)){
						ni-=di[d];
						nj-=dj[d];
				}
		}
	return;
}

bool dfs(int i,int j){
    if (!in_bounds(i,j))return 1;
	if (!((vis[i][j]<1) ? vis[i][j]=1,1 : 0))return 0;
	for (int d=0;d<D;d++)
        if(dfs(nxti[i][j][d],nxtj[i][j][d]))
            return 1;
    return 0;
}

bool impossible(){
    for (int i=1;i<=r;i++)
	for (int j=1;j<=c;j++)
		if(a[i][j] == '.')
            if(memset(vis,0,sizeof(vis)),!dfs(i,j))
                return 1;
    return 0;
}

string BFS(){
    mov.clear();
    mov[s] = "";
    while (!q.empty()) q.pop();
    for (q.push(s); !q.empty(); q.pop()){
        u=q.front();
        int sz_u=((int)(u).size());
        if (!sz_u) return mov[u];
        for (int d=0;d<D;d++){
            v.clear();
            for (int k_u=((int)(u).size()),k=0;k<k_u;k++){
                int ni=nxti[u[k].first][u[k].second][d];
                int nj=nxtj[u[k].first][u[k].second][d];
                if(in_bounds(ni, nj)) v.push_back(pnt(ni, nj));
            }
            min_represent(v);
            if (mov.find(v) == mov.end()){
				 mov[v]=mov[u]+dc[d];
				 q.push(v);
            }
        }
    }
    return "";
}


string min_moves(){
    return impossible()?"Impossible":BFS();
}

void solve(int tt){
	Read();
	Init();
	printf("Case %d: %s\n",tt,min_moves().c_str());
	return;
}

int main() {
    int T;scanf("%d",&T);int tt=0;
    while (T--){
		solve(++tt);
    }
    return 0;
}