Problem D - Seven Seas

Time Limit: 1 second

Seven Seas is a nice game where you are the captain of a battle ship. You are in the middle of the ocean and there are some enemy ships trying to catch you. Your mission is to run away from them. Destroy the enemies if you can!

The game is played on a 9x8 board and you can move in all the 8 directions, one step each time. You move first, then the enemy ships move. The enemy ships are pretty dumb, so that they will always move to the closest position they can get to you, even if that position will destroy their ship. A ship is destroyed if it moves to a cell that contais a rock. If two enemy ships move to the same cell they are also destroyed and their remains will stay in that cell so that if another ship try to move there it will be destroyed too.

If an enemy ship reaches your ship, you are dead and the game is over.

Input

The first line of the input contains the number of scenarios. Each scenarion consists of a 9x8 board of charachters. Your ship is represented by a 'S' on the board and the enemy ships are represented by a 'E'. The rocks are represented by a '#' and the '.' represents the sea. See the sample input to see the specific input format.

There will be at least one and at most nine enemy ships. There will be an empty line between two scenarios.

Output

For each scenario you must find out if it is possible to destroy all the enemy ships in less than 10 steps. If that is the case, you must print one line containing the string: I'm the king of the Seven Seas!. Otherwise, you must print one line with the string: Oh no! I'm a dead man!.

Sample Input

3
........
.E.#....
...E....
..#.....
........
........
..S.....
........
........

........
.E.E....
...S....
.E..E...
........
........
........
........
........

E......#
........
........
........
........
........
........
.......S
#.......

Sample Output

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!

---

Problem setter: Jo�o Paulo Fernandes Farias

題目描述：

問能不能在 10 步內(不含)，將所有敵方船摧毀。

兩艘船的移動可以八個方向，我方只有一艘船，敵方最多 9 艘。

我方先進行一次移動，而對方就像磁石一樣，傻傻地往最鄰近我方的格子移動一格，

因此很容易撞上障礙物，又或者敵方兩艘撞在一起，當 2 艘船撞在一起時，他們會變成新的障礙物。

當然最後我方要倖存，對方要全滅。

題目解法：

嘗試所有情況進行 BFS 搜索，移動不能超過這個 9x8 格子。

海不是上下連起來的那種情況。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int dx[] = {0,0,1,1,1,-1,-1,-1};
int dy[] = {1,-1,0,1,-1,0,1,-1};
int bfs(string st) {
    int i, j, k;
    int sx, sy, ex[9], ey[9], e, eex[9], eey[9];
    int tsx, tsy, tex, tey;
    int step;
    string nt;
    queue<string> Q;
    map<string, int> R;
    Q.push(st), R[st] = 1;
    while(!Q.empty()) {
        st = Q.front(), Q.pop();
        step = R[st];
        if(step == 10)   continue;
        e = 0;
        for(i = 0; i < 9; i++) {
            for(j = 0; j < 8; j++) {
                if(st[i*8+j] == 'S')
                    sx = i, sy = j;
                if(st[i*8+j] == 'E')
                    ex[e] = i, ey[e] = j, e++;
            }
        }
        if(e == 0)
            return step;
        //
        for(i = 0; i < 8; i++) {
            tsx = sx+dx[i], tsy = sy+dy[i];
            if(tsx < 0 || tsy < 0 || tsx >= 9 || tsy >= 8)
                continue;
            if(st[tsx*8+tsy] != '.')
                continue;
            for(j = 0; j < e; j++) {
                tex = ex[j]+dx[0], tey = ey[j]+dy[0];
                for(k = 1; k < 8; k++) {
                    if(abs(ex[j]+dx[k]-tsx)+abs(ey[j]+dy[k]-tsy) < abs(tex-tsx)+abs(tey-tsy)) {
                        tex = ex[j]+dx[k];
                        tey = ey[j]+dy[k];
                    }
                }
                eex[j] = tex, eey[j] = tey;
            }
            nt = st;
            for(j = 0; j < 72; j++)
                if(nt[j] == 'S' || nt[j] == 'E')
                    nt[j] = '.';
            nt[tsx*8+tsy] = 'S';
            int lost = 0;
            for(j = 0; j < e; j++) {
                if(nt[eex[j]*8+eey[j]] == 'S') {
                    lost = 1;break;
                }
                if(nt[eex[j]*8+eey[j]] == 'E')
                    nt[eex[j]*8+eey[j]] = '#';
                if(nt[eex[j]*8+eey[j]] == '.')
                    nt[eex[j]*8+eey[j]] = 'E';
            }
            if(lost)    continue;
            if(R.find(nt) == R.end()) {
                R[nt] = step+1;
                Q.push(nt);
            }
            /*for(j = 0; j < 9; j++, puts(""))
                for(k = 0; k < 8; k++)
                    putchar(nt[j*8+k]);
            puts("---");*/
        }
    }
    return -1;
}
int main() {
    int testcase, i;
    char g[9][9];
    scanf("%d", &testcase);
    while(testcase--) {
        for(i = 0; i < 9; i++)
            scanf("%s", g[i]);
        string st = "";
        for(i = 0; i < 9; i++)
            st += g[i];
        int ret = bfs(st);
        if(ret == -1)
            puts("Oh no! I'm a dead man!");
        else
            puts("I'm the king of the Seven Seas!");
        //printf("%d\n", ret);
    }
    return 0;
}