题目链接

题意

A要从（0,0）到（m,n），A有体力值D,每秒都会消耗体力值1，有K座炮塔，每座炮塔都会发射子弹，给出炮塔射击的方向，并且具有一个射击周期，和子弹的速度。

  • 当且仅当子弹在整数坐标（时间以1秒为最小单位）是才能击中A
  • 炮塔会挡住子弹
  • 人可以站着不动
  • 当终点有炮塔的时候不能到达
    求A能否到达终点，如果能输出最短时间。

解题思路

写这题的时候感觉有点掉头发。。。
首先预处理子弹会在哪个位置有效击中，用一个三维数组来保存信息，对于每个子弹，先求出子弹能到达的最远位置，然后在0~d的时间内求，然后再用bfs来搜索可行的路线，当第一次能到达（m,n）就是所求答案。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<vector>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring>
#include<functional>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> PII;
const int maxm = 1005;
const int maxn = 105;
int dx[] = {1,0,0,-1,0};
int dy[] = {0,1,-1,0,0};
char dir[] = {‘S’,‘E’,‘W’,‘N’};
struct Node 
{
    int x,y;
    int step;
    Node(){}
    Node(int a,int b,int c):x(a),y(b),step(c){}
};
struct Castle 
{
    char c;
    int t,v;
    int x,y;
};
Castle E[maxn];
bool mmp[maxm][maxn][maxn];
bool B[maxn][maxn],vis[maxm][maxn][maxn];
int m,n,k,d;

void init()
{
    for(int it=0;it<k;it++){
        int di;
        int X,Y;
        for(int i=0;i<4;i++) 
            if(dir[i]==E[it].c)
                di = i;
        for(int i=1;i<maxm;i++){
            int nx = E[it].x + dx[di]i;
            int ny = E[it].y + dy[di]i;
            if(nx < 0 || nx > m || ny <0 || ny > n || B[nx][ny]){
                X = nx,Y = ny;          //子弹最远能到达的坐标
                break;
            }
        }
        if(E[it].c==‘S’){
            for(int j=0;j<=d;j+=E[it].t){   //从0到d，子弹能打中的位置
                int t = 0;
                for(int l = E[it].x+E[it].v;l<X;l+= E[it].v){
                    t++;
                    if(j+t < d)
                        mmp[j+t][l][E[it].y] = 1;
                }
            }
        }else if(E[it].c==‘N’){
            for(int j=0;j<=d;j+=E[it].t){
                int t = 0;
                for(int l=E[it].x-E[it].v;l>X;l-=E[it].v){
                    t++;
                    if(j+t<d)
                    mmp[j+t][l][E[it].y] = 1;
                }
            }
        }else if(E[it].c==‘E’){
            for(int j=0;j<=d;j+=E[it].t){
                int t = 0;
                for(int r = E[it].y+E[it].v;r < Y;r += E[it].v){
                    t++;
                    if(t+j<=d)
                    mmp[j+t][E[it].x][r] = 1;
                }
            }
        }else{
            for(int j=0;j<=d;j+=E[it].t){
                int t = 0;
                for(int r = E[it].y-E[it].v;r>Y;r-=E[it].v){
                    t++;
                    if(j+t<d){
                        mmp[j+t][E[it].x][r] = 1;
                    }
                }
            }
        }
    }
}

void bfs()
{
    queue<Node> Q;
    Node b(0,0,0);
    Q.push(b);
    vis[0][0][0] = 1;
    while(!Q.empty()){
        Node t = Q.front();
        Q.pop();
        if(t.step>=d)break;
        if(t.x==m&&t.y==n){
            cout << t.step << endl;
            return ;
        }
        for(int i=0;i<5;i++){
            int nx = t.x + dx[i];
            int ny = t.y + dy[i];
            int step = t.step+1;
            if(nx <0||nx >m||ny<0||ny>n||vis[step][nx][ny])continue;
            if(B[nx][ny])continue;
            if(mmp[step][nx][ny])continue;
            vis[step][nx][ny] = 1;
            Q.push(Node(nx,ny,step));
        }
    }
    cout << “Bad luck!”<< endl;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> m >> n >> k >> d){
        memset(B,0,sizeof(B));
        memset(mmp,0,sizeof(mmp));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<k;i++){
            cin >> E[i].c >> E[i].t >> E[i].v >> E[i].x >> E[i].y;
            B[E[i].x][E[i].y] = 1;
        }
        init();
        if(B[m][n]){    //当终点有炮塔的时候不能到达
            cout << “Bad luck!”<< endl;
        }else
            bfs();
    }

    return 0;
}