c语言捉迷藏,2013腾讯马拉松初赛 ACM 小明系列故事——捉迷藏

[c]代码库/*

2013腾讯马拉松初赛第5场

1004 小明系列故事——捉迷藏

Time Limit: 0.2 Seconds Memory Limit: 32768K

小明的妈妈生了三个孩子，老大叫大明， 老二叫二明， 老三...， 老三自然就叫小明了。

一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：

只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。

为了简单起见，把公园看成是n行m列的矩阵，其中’S’表示小明，’D’表示大名，’E’表示二明，’X’表示障碍物，’.’表示通路。这里，我们把发现定义为，可以直接看到对方， 也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假设，大明，二明藏好以后就不会再改变位置，小明每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。

Input

测试数据第一行是一个正整数T，表示有T组测试数据。

每一组测试数据首先是三个正整数n,m,t，分别表示行数、列数和规定的时间，接下来n行，每行m个上述的字符，并且保证有且只有一个’S’，一个’E’，一个’D’。

[Technical Specification]

T < 200

3 <= n, m <= 100

0 <= t <= 100

Output

每组先输出一行Case c:(c表示当前的组数，从1开始计数)；

接下来一行，如果小明可以在规定时间内找到所有的人，则输出最少需要的时间，否则输出-1。

Sample Input

3

5 6 3

XXD...

....E.

....X.

....S.

......

5 6 3

XDX...

....E.

......

....S.

......

5 6 8

XXDX..

.XEX..

......

....S.

......

Sample Output

Case 1:

-1

Case 2:

3

Case 3:

-1

*/

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef __int64 LL;

#define eps 10e-9

#define inf 0x3f3f3f3f

const int maxn = 100 + 20;

const int mod = 1000000000 + 7;

char ma[maxn][maxn];

bool vis[maxn][maxn][2][2];

struct node {

int x, y, step;

int f1, f2;

} s_pos, d_pos, e_pos;

int dx[] = {1, -1, 0, 0};

int dy[] = {0, 0, 1, -1};

int n, m, t;

void cheak(node &a, node b) {

if(a.x == b.x) {

int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;

for(int i = start + 1; i < end; i++) {

if(ma[a.x][i] != '.') {

find = 1;

break;

}

}

if(!find) {

a.f1 = 1;

}

}

if(a.y == b.y) {

int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;

for(int i = start + 1; i < end; i++) {

if(ma[i][a.y] != '.') {

find = 1;

break;

}

}

if(!find) {

a.f1 = 1;

}

}

}

void cheak2(node &a, node b) {

if(a.x == b.x) {

int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;

for(int i = start + 1; i < end; i++) {

if(ma[a.x][i] != '.') {

find = 1;

break;

}

}

if(!find) {

a.f2 = 1;

}

}

if(a.y == b.y) {

int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;

for(int i = start + 1; i < end; i++) {

if(ma[i][a.y] != '.') {

find = 1;

break;

}

}

if(!find) {

a.f2 = 1;

}

}

}

int bfs() {

memset(vis, false, sizeof(vis));

queue q;

cheak(s_pos, d_pos);

cheak2(s_pos, e_pos);

vis[s_pos.x][s_pos.y][s_pos.f1][s_pos.f2] = true;

q.push(s_pos);

while(!q.empty()) {

node now = q.front();

q.pop();

if(now.f1 > 0 && now.f2 > 0) {

return now.step;

}

for(int i = 0; i < 4; i++) {

node next = now;

next.x += dx[i];

next.y += dy[i];

if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && !vis[next.x][next.y][next.f1][next.f2]

&& ma[next.x][next.y] == '.') {

vis[next.x][next.y][next.f1][next.f2] = true;

next.step++;

if(!next.f1)

cheak(next, d_pos);

if(!next.f2)

cheak2(next, e_pos);

if(next.step <= t)

q.push(next);

}

}

}

return 10000;

}

int main() {

int T, ca = 1;

cin >> T;

while(T--) {

scanf("%d %d %d", &n, &m, &t);

for(int i = 0; i < n; i++)

scanf("%s", ma[i]);

for(int i = 0; i < n; i++) {

for(int j = 0; j < m; j++) {

if(ma[i][j] == 'S') {

s_pos.x = i;

s_pos.y = j;

s_pos.step = 0;

s_pos.f1 = s_pos.f2 = 0;

}

if(ma[i][j] == 'D') {

d_pos.x = i;

d_pos.y = j;

}

if(ma[i][j] == 'E') {

e_pos.x = i;

e_pos.y = j;

}

}

}

int now = bfs();

printf("Case %d:\n", ca++);

if(now <= t) printf("%d\n", now);

else printf("-1\n");

}

return 0;

}