题解：AT_abc203_e [ABC203E] White Pawn

· · 题解

有一点小细节的模拟题

简述题意：

给定n、m，在 2 n + 1 行、2 n + 1 列的网格中有 m 个黑棋子，行、列均编号 0—2n，从（0，n）出发，遵循以下三种移动方式：

（绿色圆点为当前位置，红色箭头指向可移动到的位置，黑色圆点为黑棋子。）

问最后一行中有几个位置可以通过上述移动方式到达。

分析样例： ①(0, n) -> (1, 1)

②(1, 1) -> (2, 0), (2, 1)

③(2, 0) -> (3, 0)

(2, 1) -> (3, 1)

④(3, 0) -> (4, 0)

(3, 1) -> (4, 1), (4, 2)

即(4, 0), (4, 1), (4, 2)符合题意

考虑搜索？

从上面样例看出到达最后一行一定走了2 * n步，且每一步都是从上一步到达的点开始进行判断左下、正下、右下三个方向的。DFS启动，然鹅 n≤1e9，T&M。

优化一下

观察上面样例，第一我们发现是逐行判断的，第二只有遇到黑棋子时才有可能改变方向。因此我们可以直接对黑棋子的位置按照 行序号递增的顺序排序，对有黑棋子逐行运算。

此时我们把问题从“判断一个点能到达的下一个位置”转换成了“当前黑棋子所在的点能不能到达”，进而变成了“当前黑棋子所在的这一列是否是可走状态”。所以用map维护一下当前列是否可走 、cnt记录可走列数即可，初始状态为第 n 列可走(true)，其余全不可走(false)，cnt = 1，由于map开在主函数外面时初始值均为 0，所以不需要进行初始化。

如果黑棋子所在列为true，更新该列为false，cnt--；

如果黑棋子所在列相邻两列中任一为true，更新当前列为true，如果当前列原本为false，cnt++。（此处如有疑问见“细节处理”）

细节处理：

情况1：

绿色为可走到的位置

对于判断(2, 1)的黑棋子，如果先判断其相邻列，将其所在列更新为true，再判断其所在列，将其所在列更新为false显然与事实不符。故先判断所在列再判断相邻列。

情况2：

判断(2, 1)的黑棋子后会将第 1 列改为false，此时再判断(2, 2)的黑棋子显然不能将第 2 列变为true，这也与事实不符。故可以先将一行内的黑棋子位置全判断完，最后对这一行统一做修改。

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NUM = 2e5 + 10;
ll n, m, cnt = 1;
struct POS {ll x, y;} dat[NUM];
bool cmp (POS a, POS b) {return a.x == b.x? a.y < b.y: a.x < b.x;}
// 先按行号排序，再按列号排序，其实只需要排行即可。
map<ll, bool> ok;
struct MEM {ll pos, wgh; bool typ;}; 
queue<MEM> que;// 用于记录一行内的黑棋子造成的影响。 
int main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    cin >> n >> m; ok[n] = true;// 输入，map初始化。 
    for (ll i = 1; i <= m; i++) cin >> dat[i].x >> dat[i].y;
    sort (dat + 1, dat + 1 + m, cmp);
    for (ll i = 1; i <= m;) {
        ll tmp = dat[i].x;
        while (dat[i].x == tmp) {// 找同一行内的黑棋子。 
            if (ok[dat[i].y]) que.push({dat[i].y, -1, false});// true->false。 
            if (ok[dat[i].y + 1]
             || ok[dat[i].y - 1]) que.push({dat[i].y, 1, true});// false->true。 
        i++;}
        while (!que.empty()) {
            MEM t = que.front(); que.pop();
            if (ok[t.pos] ^ t.typ) cnt += t.wgh;// 如果该列的状态发生改变才影响cnt。 
            ok[t.pos] = t.typ;
        }// 统一修改。 
    }
    cout << cnt;
    return 0;
}