文章目录
题目分析错因代码
题目
[NOI Online #2 入门组] 荆轲刺秦王
分析
记忆化 BFS。记录
T
[
x
]
[
y
]
[
c
1
]
[
c
2
]
(
c
1
≤
C
1
,
c
2
≤
C
2
)
T[x][y][c_1][c_2]\ (c_1 \leq C_1, c_2 \leq C_2)
T[x][y][c1][c2] (c1≤C1,c2≤C2) 表示能否恰好用
c
1
c_1
c1 次隐身和
c
2
c_2
c2 次瞬移从起始位置走到
x
x
x 行
y
y
y 列，
N
u
m
[
x
]
[
y
]
Num[x][y]
Num[x][y] 表示走到
x
x
x 行
y
y
y 列保证最短时间（BFS 本身就能保证）下的最小
c
1
+
c
2
c_1 + c_2
c1+c2 值。
错因
freopen 没删；输入用的 getchar 本地运行结果跟 OJ 不同，应该用 scanf 读入字符数组；题意读错，以为瞬移路径上不能被观察到，实际上瞬移过程无视守卫；居然没想过用 BFS，一上来就 DFS；没想到用差分处理曼哈顿距离的区间修改单点查询。
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
const int MAXC
= 15;
const int MAXN
= 350;
const int INF
= 0x3f3f3f3f;
inline int Abs(const int &x
) {
return x
< 0 ? -x
: x
;
}
const int Dir
[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
int N
, M
, C1
, C2
, D
;
int Num
[MAXN
+ 5][MAXN
+ 5];
int Map
[MAXN
+ 5][MAXN
+ 5], V
[MAXN
+ 5][MAXN
+ 5];
bool T
[MAXN
+ 5][MAXN
+ 5][MAXC
+ 5][MAXC
+ 5];
struct Node
{
int x
, y
, t
, c1
, c2
;
Node(int _x
= 0, int _y
= 0, int _t
= 0, int _c1
= 0, int _c2
= 0) {
x
= _x
, y
= _y
, t
= _t
, c1
= _c1
, c2
= _c2
;
}
bool operator < (const Node
&other
) const {
if (t
!= other
.t
) return t
< other
.t
;
else if (c1
+ c2
!= other
.c1
+ other
.c2
)
return c1
+ c2
< other
.c1
+ other
.c2
;
else return c1
< other
.c1
;
}
};
inline bool Ok(const int &x
, const int &y
) {
return x
>= 1 && x
<= N
&& y
>= 1 && y
<= M
&& Map
[x
][y
] <= 0 && Map
[x
][y
] != -1;
}
int main() {
int X
, Y
, A
, B
;
scanf("%d%d%d%d%d", &N
, &M
, &C1
, &C2
, &D
);
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= M
; j
++) {
char str
[10]; scanf("%s", str
);
int len
= strlen(str
);
for (int k
= 0; k
< len
; k
++) {
char c
= str
[k
];
if (c
== '.') Map
[i
][j
] = 0;
else if (c
== 'S') Map
[A
= i
][B
= j
] = -1;
else if (c
== 'T') Map
[X
= i
][Y
= j
] = -2;
else Map
[i
][j
] = Map
[i
][j
] * 10 + (c
^ 48);
}
for (int x
= 0; x
<= Map
[i
][j
] - 1; x
++) {
int y
= Map
[i
][j
] - x
- 1;
if (i
- x
>= 1)
V
[i
- x
][std
::max(1, j
- y
)]++, V
[i
- x
][std
::min(M
, j
+ y
) + 1]--;
if (i
+ x
<= M
)
V
[i
+ x
][std
::max(1, j
- y
)]++, V
[i
+ x
][std
::min(M
, j
+ y
) + 1]--;
}
}
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= M
; j
++)
V
[i
][j
] += V
[i
][j
- 1];
std
::queue
<Node
> Q
;
Q
.push(Node(A
, B
, 0, 0, 0));
Num
[A
][B
] = 0;
memset(Num
, 0x3f, sizeof Num
);
Node Ans
= Node(X
, Y
, INF
, INF
, INF
);
while (!Q
.empty()) {
Node u
= Q
.front(); Q
.pop();
if (u
.x
== X
&& u
.y
== Y
) {
if (Ans
.t
< u
.t
)
break;
Ans
= std
::min(Ans
, u
);
}
int tx
= 0, ty
= 0;
for (int p
= 0; p
<= 1; p
++) {
if (u
.c1
+ p
> C1
)
continue;
u
.c1
+= p
;
for (int i
= 0; i
< 8; i
++) {
if (i
< 4 && u
.c2
< C2
) {
tx
= u
.x
+ Dir
[i
][0] * D
, ty
= u
.y
+ Dir
[i
][1] * D
;
if (Ok(tx
, ty
) && !T
[tx
][ty
][u
.c1
][u
.c2
+ 1])
if ((!V
[tx
][ty
] || p
) && Num
[tx
][ty
] > u
.c1
+ u
.c2
+ 1) {
Num
[tx
][ty
] = u
.c1
+ u
.c2
+ 1;
T
[tx
][ty
][u
.c1
][u
.c2
+ 1] = true;
Q
.push(Node(tx
, ty
, u
.t
+ 1, u
.c1
, u
.c2
+ 1));
}
}
tx
= u
.x
+ Dir
[i
][0], ty
= u
.y
+ Dir
[i
][1];
if (Ok(tx
, ty
) && !T
[tx
][ty
][u
.c1
][u
.c2
])
if ((!V
[tx
][ty
] || p
) && Num
[tx
][ty
] > u
.c1
+ u
.c2
) {
Num
[tx
][ty
] = u
.c1
+ u
.c2
;
T
[tx
][ty
][u
.c1
][u
.c2
] = true;
Q
.push(Node(tx
, ty
, u
.t
+ 1, u
.c1
, u
.c2
));
}
}
}
}
if (Ans
.t
== INF
)
printf("-1");
else
printf("%d %d %d", Ans
.t
, Ans
.c1
, Ans
.c2
);
return 0;
}
