题目描述:
三体--人类的末日之战
这一天终于来了,人类监测到三体文明发射的探测器-水滴即将抵达太阳系,为了各方政治势力权衡,同时为了彰显太空军的军威,人类全体舰队从木星启航,在太阳系中全军摆好阵势拦截水滴。
水滴抵达了太阳系,这时水滴的尾部开始出现向外扩张的圆环,同时伴随着太阳核心板的超高温,水滴冲向了舰队的一角,在太空中未经减速便拐出了一个30度的锐角之后,一条两倍于第三宇宙速度的光影,从“无限边疆号”起始,顺着延长线方向,穿过一整列的太空舰队,每一个撞击点精确锁定了聚变燃料舱,热核爆炸的火球依次出现在舰队之中,宇宙中下起了炽热的金属岩浆暴雨,百艘战舰像一挂鞭炮,分钟之内全部炸完。水滴就像一枚死神的绣花针,灵巧的上下翻飞,达到10倍第三宇宙速度的水滴肆意屠杀,就这样,水滴用了一分十八秒飞行了两千公里,贯穿了整个联合舰队。
樯橹之间,灰飞烟灭。人类舰队,全军覆没!就这样,毁灭人类全部太空力量的,只是三体世界中一粒小小的探测器,而采用的方式,是最为原始粗暴的方式—撞击!这就是末日之战,毁灭你,与你何干?
给你一个m×n的点矩阵,矩阵中有一个字母W,若干个字母S,其余均为符号“#”。其中W代表探测器水滴,S代表人类的宇宙飞船,宇宙中的其余物质,用“#”来表示。探测器—水滴可以通过撞击的方式,摧毁人类的宇宙飞船。水滴的运动方式是,每次可以在矩阵中向上、向下、向左、向右移动一个单位距离。因为人类人工智能科技不发达,因此直到水滴摧毁所有的飞船,人类还没有反应过来,因此认为在所有的飞船是不动的。现在,水滴开始发动攻击,从初始位置开始,到撞毁最后一艘人类战舰,水滴可以移动的最短距离是多少?
样例输入:
3 4
#S##
###W
###W
9 10
#W####S##
#########
##S###S##
#####S###
#########
####S####
#########
S########
######S##
样例输出:
4
28
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int M, N;
typedef struct xxyy {
int x;
int y;
}xxyy;
xxyy dist[1002];
char map[32][32];
int book[1002], min, tag;
void dfs(int i, int ans, int flag) {
int j, flag2 = 0, ans2;
if (flag >= tag) {
if (min > ans)
min = ans;
return;
}
for (j = 1; j <= tag; j++) {
if (book[j]) {
book[j] = 0;
ans2 = ans + abs(dist[j].x - dist[i].x) + abs(dist[j].y - dist[i].y);
flag2 = flag + 1;
dfs(j, ans2, flag2);
book[j] = 1;
}
}
}
int main() {
int i, j;
while (~scanf("%d%d", &M, &N), M + N){
tag = 0;
min = 999999999;
memset(dist, 0, sizeof(dist));
memset(book, 0, sizeof(book));
for (i = 0; i < M; i++) {
scanf("%s", map[i]);
for (j = 0; j < N; j++) {
if (map[i][j] == '#') {
dist[++tag].x = j;
dist.y = i;
book = 1;
}
else if (map[i][j] == 'E') {
dist[0].x = j;
dist[0].y = i;
}
}
}
dfs(0, 0, 0);
printf("%d\n", min);
}
return 0;
}