题目描述

你有两个机器人，站在平面上的两个点上，（x1,y1） (x2,y2)

机器人每次可以向上下左右四个方向中的某个方向移动一个单位

你给两个机器人发送了同样的指令序列，一个指令需要花一秒执行
但是两个机器人可能有一些bug，他们各自可能会忽略掉一些指令，可能会忽略所有指令，也可能一个指令都不会忽略

两个机器人如果移动到了同一个位置就会爆炸

你的任务是判断是否有可能爆炸

输入描述: 

第一行输入四个整数x1,y1,x2,y2
-25 ≤ x1,y1,x2,y2 ≤ 25
第二行输入一个字符串表示指令序列,包含'U','R','L','D'四种字符

输出描述: 

如果可能爆炸输出"Explosion"
否则输出"Safe"

思路（未优化）:用一个dis记录两个机器人之间的距离，距离为0时爆炸。
容易证得若某一个指令使得dis增大时，这一个指令一定是无效的，当这一个指令无效时，将两个机器人的位置恢复成上一次的状态再继续遍历之后的指令
贪心思想即为：每一次都寻求最短距离（最优解），如果距离反而增大（该解不是最优）即舍去，直到求出结果（安全或是爆炸）为止

代码如下（未优化）：
#include<stdio.h>
#include<string.h>
#include<math.h>
int main() {
    int i,x1,x2,y1,y2,len;
    double dis,dist;
    char s[120];
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    dis=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    scanf("%s",s);
    len=strlen(s);
    for(i=0; i<len; i++) {
        if(dis==0) break;
        if(s[i]=='U') y1++;
        if(s[i]=='R') x1++;
        if(s[i]=='L') x1--;
        if(s[i]=='D') y1--;
        dist=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
        if(dist<dis) {
            dis=dist;
            if(dis==0) break;
        } else {   //发现不是最优解之后的撤销至上一个指令的状态
            if(s[i]=='U') y1--;
            if(s[i]=='R') x1--;
            if(s[i]=='L') x1++;
            if(s[i]=='D') y1++;
        }
    }
    for(i=0; i<len; i++) {
        if(dis==0) break;
        if(s[i]=='U') y2++;
        if(s[i]=='R') x2++;
        if(s[i]=='L') x2--;
        if(s[i]=='D') y2--;
        dist=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
        if(dist<dis) {
            dis=dist;
            if(dis==0) break;
        } else {  //发现不是最优解之后的撤销至上一个指令的状态
            if(s[i]=='U') y2--;
            if(s[i]=='R') x2--;
            if(s[i]=='L') x2++;
            if(s[i]=='D') y2++;
        }
    }
    if(dis==0) printf("Explosion\n");
    else printf("Safe\n");
    return 0;
}

思路（优化）:因为U与D，L与R对于同一个机器人来说互为相反的指令，但是对于两个机器人来说，只要一个忽略L，另一个忽略R，或是一个忽略U，另一个忽略D，那么两个机器人之间的距离可以减少2，相当于一个机器人靠近另一个机器人2个单位的距离，如此，可以简化代码，假设一个机器人不动，另一个机器人对于U或D,L或R执行相同的靠近操作即可

优化之后的代码如下：
#include<stdio.h>
#include<string.h>
#include<math.h>
int main() {
    int i,x1,x2,y1,y2,xt=0,yt=0,len;
    char s[120];
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    scanf("%s",s);
    len=strlen(s);
    x2=(abs)(x2-x1);
    y2=(abs)(y2-y1);  //相当于将一个机器人放在原点，另一个机器人放在(x,y)（x>0且y>0）,方便之后操作
    for(i=0; i<len; i++) {
        if(s[i]=='U' || s[i]=='D') yt++;
        if(s[i]=='R' || s[i]=='L') xt++;
        if(yt>=y2 && xt>=x2){
            printf("Explosion\n");
            return 0; //此处直接退出，再次缩短程序运行时间（虽然不缩短时间也能够AC）
        }
    }
    printf("Safe\n");
    return 0;
}