Atcoder abc243
https://atcoder.jp/contests/abc243/tasks
Ex - Builder Takahashi (Enhanced version)
给定S
,G
,O
,.
组成的高h,宽w的矩阵, 其中S和G分别出现且仅出现一次
S起点
G终点
.
可以建墙
O
不可建墙
四临移动
问
- 最少建立多少墙可以让无法从S到G
- 满足最少墙时的方案数 mod 998244353
范围
h [2,100]
w [2,100]
4s
1024mb
我的思路
首先想到的是 直接建一个竖着或这横着的, 这样隔开就行了
又想到, 直接把起点或者终点围起来
那么问题就是能不能围住
那么先不管多少, 就把所有能建的全建立完, 那能走的只有4临可达的不能建的
所以判断能否很好判断
那么就是 最小代价的围
感觉不会超过100
但想了下要是能建立的是个蛇形, 那还是会很长接近平方
反正问题变成平面上一堆4临连在一起的S, 和一堆4临连在一起的G
要画圈/线 把两堆隔开, 然后有些不能画线的地方
1 |
|
注意到虽然 不能画的x与s不相连, 但是依然可能影响围住s的大小
没啥想法, 感觉直接围起来 保证不了最小
1 |
|
如果围完以后, 找 两点最短更新,需要保证包裹住
需要A星 一类的启发式吗?
但如果上了启发 后面统计又不太行了
甚至可能包裹和 隔断等价
1 | g |
没有头绪