Problem D
The Rock
Input: standard input
Output: standard output
Time Limit: 12 seconds
Memory Limit: 32 MB
A group of terrorists have taken hostages on the former prison island Alcatraz (now a tourist attraction) outside San Francisco, and is demanding a big ransom from the US government. If they are not paid within 40 hours, they will launch 15 rockets of V.X. poison gas at San Francisco, each rocket capable of killing 70,000 people.
The Pentagon is planning on sending a SEAL team to Alcatraz to destroy the rockets. They intend to penetrate the island through the tunnels under the prison building, but because the prison has been rebuilt so many times, all the maps of the tunnels are useless. The only man who can help them is John Mason, a former inmate who once successfully escaped from Alcatraz through the tunnels.
However, Mason is getting old so he doesn't remember all the details of the tunnels. More precisely, he knows that there is exactly one wall whose location he doesn't remember. Since they're running out of time, they want to make sure that they take a path which will guarantee the shortest possible time to reach the exit of the tunnels no matter where this extra wall is. Since you're the top program writer at the Pentagon, it's your job to write the program to find this shortest path!
For simplicity, we can assume that the tunnels below Alcatraz can be described as a rectangular grid, where each grid square is either wall or open space, and walking is permitted only between adjacent non-wall squares. Two squares are adjacent if they have one side in common. The additional, unknown, wall occupies exactly one square, and the team will not notice this wall until they've reached an adjacent square to it.
Example:
..X..... ........ ##.##... ........ ##.##... ##.##... ........ ..E..... If the team walks straight ahead from the entrance (E), they may face a wall at row 4 column 3, in which case they have to turn around and the length of the path will be 17. It's better to walk to the right immediately, as this will ensure a path of length at most 15.
Input
The first line in the input will contain one integer n (n ≤ 10) which is the number of maps to process. Then follows the n map descriptions.
Each map description starts with a blank line, followed by a line with two integers, describing the number of rows and columns in the map, respectively. The map then follows one row on each line. '#' is used for walls, '.' for open space, 'E' is the entrance and 'X' is the exit. The number of rows and columns in the map is at least 3 and at most 40.
You may assume that the map is valid and that there will be exactly one entrance and one exit square. You may also assume that there exist at least two disjoint paths (sharing no squares except the entrance and exit) from the entrance to the exit and that the additional wall will neither be on the entrance nor exit square.
Output
For each map, output a single line containing the length of the shortest path according to the description above.
2 8 8 ..X..... ........ ##.##... ........ ##.##... ##.##... ........ ..E..... 3 4 ..X. .##. .E.. 15 11 (Regionals 2002 Warm-up Contest, Problem setter: Jimmy Mårdell)
題意：有一個迷宮，有一個入口和出口，其中有一道隐形的牆，你不知道他在哪裡，你需要設計一種行走路線，使得最壞的情況下路徑最短。
思路：首先我們來分析一下這道“隐形”的牆怎麼讓你的情況最差。首先我們任意選擇一條路線。那麼這道牆可能出現這個路線上的任意一點，如果出現了，我們不得不繞路走，當然繞路後也要走最短的。這時候我們另外一個路徑。把每個點逐個當做是隐形的牆得出的各個路徑中最長的，就是這條路徑的最差情況。根據這些，我們得知，當我們在走的時候，我們要不斷的計算如果出現牆後的路徑是多少，我們要取這些所有路徑最大的。是以我們設計出狀态（r,c,g,h)分别表示的是所處的行、列、步數、目前“繞路走”中最常的長度。用這個狀态進行搜尋就行。我們每次隻需要取所有狀态中h最小的。還要用一個done[r][c][g]記錄從起點到達（r，c）步數為g時，最小的h值。“繞路走”的長度，我們預處理一下在（r，c）往dir方向跑碰到隐形牆而繞到終點的距離。那麼搜的時候可以直接得出h值。有了這些思路，基本就能做出來了。
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<queue>
using namespace std;
#define mp make_pair
const int maxn = 40 + 2;
const int inf = 1e8;
int n, m;
const int Move[2][4] = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
inline int row(int x) { return x / m; }
inline int col(int x) { return x%m; }
inline int getx(int r, int c) { return r*m + c; }
inline bool inRange(int r, int c) { return 0 <= r&&r < n && 0 <= c&&c < m; }
char maze[maxn][maxn];
int d[maxn*maxn];
int done[maxn*maxn][maxn*maxn];
int w[maxn*maxn][4];
int s, t;
void bfs()
{
queue<int> q;
q.push(t);
memset(d, 0x3f, sizeof(d));
d[t] = 0;
while (q.size())
{
int x = q.front(); q.pop();
int r = row(x), c = col(x);
for (int i = 0; i < 4; ++i)
{
int rr = r + Move[0][i];
int cc = c + Move[1][i];
if (!inRange(rr, cc) || maze[rr][cc] == '#') continue;
int y = getx(rr, cc);
if (d[y] <= d[x] + 1) continue;
d[y] = d[x] + 1;
q.push(y);
}
}
}
void input()
{
for (int i = 0; i < n; ++i)
{
scanf("%s", maze[i]);
for (int j = 0; j < m; ++j)
{
if (maze[i][j] == 'E') s = getx(i, j);
else if (maze[i][j] == 'X') t = getx(i, j);
}
}
memset(w, 0, sizeof(w));
for (int r = 0; r < n;++r)
for (int c = 0; c < m; ++c)
{
if (maze[r][c] != '.') continue;
maze[r][c] = '#';
bfs();
for (int k = 0; k < 4; ++k)
{
int rr = r + Move[0][k];
int cc = c + Move[1][k];
if (!inRange(rr, cc) || maze[rr][cc] == '#') continue;
int y = getx(rr, cc);
w[y][(k+2)%4] = d[y];
}
maze[r][c] = '.';
}
}
struct State
{
int g;
int h;
int x;
bool operator<(const State&st) const { return h>st.h; }
};
int Dijkstra()
{
priority_queue<State> q;
memset(done, 0x3f, sizeof(done));
State S;
S.g = 0; S.h = 0;
S.x = s;
q.push(S);
while (q.size())
{
State temp = q.top(); q.pop();
int x = temp.x, g = temp.g;
if (done[x][g] <= temp.h) continue;
if (x == t) return temp.h;
done[x][g] = temp.h;
int r = row(x), c = col(x);
for (int i = 0; i < 4; ++i)
{
int rr = r + Move[0][i];
int cc = c + Move[1][i];
if (!inRange(rr, cc) || maze[rr][cc] == '#') continue;
if (maze[rr][cc] == 'E') continue;
int y = getx(rr, cc);
State now = temp;
++now.g;
if (maze[rr][cc] == '.') now.h = max(now.h, g + w[x][i]);
else if (maze[rr][cc]=='X') now.h = max(now.h, now.g);
now.x = y;
q.push(now);
}
}
return -1;
}
void solve()
{
int ans = Dijkstra();
printf("%d\n", ans);
}
int main()
{
//freopen("input.in", "r", stdin);
int T; cin >> T;
while (T--)
{
scanf("%d%d", &n, &m);
input();
solve();
}
}