D - Escape HDU - 3533——预处理+BFS

待我称王封你为后i 2022-06-15 08:39 109阅读 0赞

Think:  
1知识:预处理+BFS  
2反思:  
1>英文读题能力需要加强，读题心态要静下来  
2>Error:数组越界  
3>Error:预移动状态推演  
4>Error:可达性状态判断错误

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    struct node {
       //记录堡垒信息
        int x, y, v, t, f;
    }kp[104];
    struct node1{
       //记录结点路径
        int x, y, step;
    };
    
    int m, n, k, eng;
    int jk[5][2] = {
       {
       0,0},{-1,0},{
       1,0},{
       0,-1},{
       0,1}};//移动状态
    bool vis[104][104][1004];///记录当前结点当前时刻是否已经访问;注意时间范围
    bool mp[104][104][1004];///预处理记录在当前的时刻不能访问的点;注意时间范围
    bool point[104][104];///堡垒位置
    
    bool Judge(int dx, int dy);///判断当前结点是否越界
    void BFS(int x, int y);///深度优先搜索
    
    int main(){
        while(scanf("%d %d %d %d", &m, &n, &k, &eng) != EOF){
            memset(mp, false, sizeof(mp));//预处理记录数组初始化
            memset(vis, false, sizeof(vis));//访问记录数组初始化
            memset(point, false, sizeof(point));//堡垒记录数组初始化
    
            for(int i = 0; i < k; i++){
                char st[4];
                scanf("%s %d %d %d %d", st, &kp[i].t, &kp[i].v, &kp[i].x, &kp[i].y);
                if(st[0] == 'N') kp[i].f = 1;//注意与移动状态数组jk[]方向对应
                else if(st[0] == 'S') kp[i].f = 2;//注意与移动状态数组jk[]方向对应
                else if(st[0] == 'W') kp[i].f = 3;//注意与移动状态数组jk[]方向对应
                else if(st[0] == 'E') kp[i].f = 4;//注意与移动状态数组jk[]方向对应
                point[kp[i].x][kp[i].y] = true;//记录堡垒位置
            }
            for(int i = 0; i < k; i++){
                int dx = kp[i].x, dy = kp[i].y, dv = kp[i].v, next = kp[i].f;
                for(int j = 1; j <= eng; j++){
                    int flag = 0;
                    dx += jk[next][0];//移动尝试
                    dy += jk[next][1];//移动尝试
                    if(!Judge(dx, dy)) break;
                    for(int l = 0; l < dv; l++){
       //判断子弹是否会在过程中遇到堡垒
                        if(point[dx-jk[next][0]*l][dy-jk[next][1]*l]){
                            flag = 1;break;
                        }
                    }
                    if(flag) break;
                    int x = j;
                    while(x <= eng){
       //目标精力范围内进行预处理
                        mp[dx][dy][x] = true;//标记当前时刻当前结点不能访问
                        x += kp[i].t;//每隔t秒子弹重新出现
                    }
                }
            }
            BFS(0, 0);
        }
        return 0;
    }
    bool Judge(int dx, int dy){
        if(dx < 0 || dx > m || dy < 0 || dy > n) return false;
        return true;
    }
    void BFS(int x, int y){
        node1 a, b;
        a.x = x, a.y = y, a.step = 0;
        queue<node1> q;
        q.push(a);//入队操作
        while(!q.empty()){
            a = q.front();
            a.step++;//预移动
            q.pop();//出队操作
            for(int i = 0; i < 5; i++){
                int dx = a.x + jk[i][0];
                int dy = a.y + jk[i][1];
                if(Judge(dx, dy) && !mp[dx][dy][a.step] && !point[dx][dy] && !vis[dx][dy][a.step]){
       ///判断可访问性
                    vis[dx][dy][a.step] = true;//标记当前时刻当前结点已访问
                    if(dx == m && dy == n) {
                        printf("%d\n", a.step);return;
                    }
                    if(a.step+1 > eng) continue;//判断目标精力是否超出范围
                    b.x = dx, b.y = dy, b.step = a.step;
                    q.push(b);//入队操作
                }
            }
        }
        printf("Bad luck!\n");
    }

[vjudge]: https://vjudge.net/contest/161869#problem/D