题目描述:
三体--人类的末日之战
这一天终于来了,人类监测到三体文明发射的探测器-水滴即将抵达太阳系,为了各方政治势力权衡,同时为了彰显太空军的军威,人类全体舰队从木星启航,在太阳系中全军摆好阵势拦截水滴。
水滴抵达了太阳系,这时水滴的尾部开始出现向外扩张的圆环,同时伴随着太阳核心板的超高温,水滴冲向了舰队的一角,在太空中未经减速便拐出了一个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;
}
Last modification:December 7th, 2019 at 11:30 pm
如果觉得我的文章对你有用,请随意赞赏