lightoj1426 Blind Escape

構想:r*cのgridがあって、中には2種類の文字があって、'#'は壁を表して、通り抜けてはいけません、'.'表示free、通り抜けることができて、今この中に1人の盲人がいて、彼は東南西北の4つの方向に歩くことができて、あなたの与えた指令に頼って出てくる必要があって、もし出てこないならばImpossibleで、さもなくば出力が最も短くて辞書の順序が最も小さい命令列です.
明らかに検索ですが、もちろん出られないのが一番判断したほうがいいです.ポイントごとに検索すればいいです.最後に判断します.問題は出てくるときにどうやって探すかです.
まずqueueの中の状態は何ですか.ここでは単一の点ではなく点セットであるべきです.問題は人がその点にいてもこの命令に従って出てくることができることを要求しているので、各点に対して同時に移動し、次の点セットの状態に達し、この状態が現れたかどうかを判断します.ない場合は前の状態からこの状態+方向文字です.最後に出てくる条件はこの状態にgridの中の点が含まれていないことであり、これが最後の答えである.
ここでは状態のhashに関し,それをstringにし,点をカスタマイズ(<記号をリロード)したりpairを用いたりすることができる.

// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
using namespace std;
// #define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__ )
#else
#define debug(...)
#endif
#define CLR(x) memset(x, 0,sizeof x)
#define MEM(x,y) memset(x, y,sizeof x)
#define pk push_back
template<class T> inline T Get_Max(const T&a,const T&b){return a < b?b:a;}
template<class T> inline T Get_Min(const T&a,const T&b){return a < b?a:b;}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> ii;
typedef vector<ii> vec;
const double eps = 1e-10;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int D = 4, N = 16;
const int dx[] = {0,-1,1,0};
const int dy[] = {1,0,0,-1};
const char dc[] = {'E','N','S','W'};
vec s,u,v;
queue<vec> que;
map<vec,string> mp;
char a[N][N];
bool vis[N][N];
int r, c, nxtx[N][N][4], nxty[N][N][4];
/*erase(first,last);   first last      ，first，last    */
void MinRepresent(vec& ans){
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
}
bool InBounds(int x,int y){
	return 1 <= x && x <= r && 1 <= y && y <= c;
}
void Read(){
	scanf("%d%d",&r,&c);
	for (int i = 1;i <= r;++i)
		scanf("%s",a[i] + 1);
	return ;
}
void Initation(){
	s.clear();
	for (int i = 1;i <= r;++i){
		for (int j = 1;j <= c;++j){
			if (a[i][j] == '.') s.push_back(ii(i,j));
			for (int d = 0;d < 4;++d){
				if (a[i][j] == '.'){
					int& nx = nxtx[i][j][d];
					int& ny = nxty[i][j][d];
					for (nx = i + dx[d],ny = j + dy[d];InBounds(nx,ny) && a[nx][ny] == '.';nx += dx[d],ny += dy[d]){}
					if (InBounds(nx,ny)){
						nx -= dx[d];
						ny -= dy[d];
					}					
				}
			}
		}
	}
	return ;
}
bool dfs(int x,int y){
	if (!InBounds(x,y)) return true;
	if (vis[x][y]) return false;
	vis[x][y] = true;
	for (int i = 0;i < 4;++i){
		if (dfs(nxtx[x][y][i],nxty[x][y][i])) return true;
	}
	return false;
}
bool Impossible(){
	for (int i = 1;i <= r;++i){
		for (int j = 1;j <= c;++j){
			if (a[i][j] == '.'){
				memset(vis, false,sizeof vis);
				if (!dfs(i,j)) return true;//(i,j) can not escape out of grid.
			}
		}
	}
	return false;
}
string BFS(){
	mp.clear();
	mp[s] = "";
	while(!que.empty()) que.pop();
	que.push(s);
	while(!que.empty()){
		u = que.front();
		que.pop();
		int size = (int)(u.size());
		if (size == 0) return mp[u];
		for (int i = 0;i < 4;++i){
			v.clear();
			for (int j = 0;j < size;++j){
				int first = u[j].first;
				int second = u[j].second;
				int nx = nxtx[first][second][i];
				int ny = nxty[first][second][i];
				if (InBounds(nx,ny)) v.push_back(ii(nx,ny));
			}
			MinRepresent(v);
			if (mp.find(v) == mp.end()){
				mp[v] = mp[u] + dc[i];
				que.push(v);
			}
		}
	}
	return "";
}
int main()
{	
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	int t, icase = 0;
	scanf("%d",&t);
	while(t--){
		Read();
		Initation();
		printf("Case %d: ", ++icase);
		if (Impossible()) cout << "Impossible
";
		else{
			cout << BFS() << endl;
		}
	}
	return 0;
}