cf 模拟

https://codeforces.com/contest/1236/problem/D

题意：一个n*m格子矩阵，放一个人偶在左上角向右走，只能在每个格子最多右转一次，有k个障碍物。求是否能够一次走完矩阵的所有非障碍物格然后停留在任意位置。

题解：在每个格子最多右转一次，相当于每个格子只能走一次，否则就出不来了。容易想到障碍物必须也是占据一些蛇形的片段，并且留下的位置刚好可以让人偶走一个蛇形的绕到中心，但是怎么判断障碍物的形状呢？百思不得其解遂看题解。题解表示观察到人偶撞墙或者撞障碍物必转向（自己走过的路也是墙）。然后暴力模拟一遍，每次在数据结构里面搜索前进方向上最近的墙/障碍物，走到它面前。至多进行n+m次。

所以选择一个结构就是set，维护行和列分别两堆set，一个障碍物同时插入行列两个set里面。然后墙/自己走过形成的墙就设置一个最值把多走的部分截断就可以了。判断答案的方法就是暴力统计走过的格子数是否等于空格数。

注：实现的时候卡在了样例4，因为会让人偶走回头路，但是也不能够简单让人偶移动0格就退出，比如一条竖线的矩阵。修复的方法是在人偶的后方一个格子塞一个障碍物。然后卡在样例9，看了dalao的代码才知道错在哪里，首先while循环的停止条件错了，不应该是d>u||r>l，应该是d>=u&&r>=l，因为是闭区间。这个改进再加上后面堵一个障碍物就可以防止原路返回了，人偶会在中间不断转圈圈。不过最简单的办法是记录人偶原地不动的次数，>=2次就break掉。

其实并不需要堵格子，记录原地不动的次数之后就不会原路返回了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

set<int> sr[100005], sc[100005];

int main() {

#ifdef KisekiPurin

    freopen("KisekiPurin.in", "r", stdin);

#endif // KisekiPurin

    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= n; ++i) {

        sr[i].insert(0);

        sr[i].insert(m + 1);

    }

    for(int i = 1; i <= m; ++i) {

        sc[i].insert(0);

        sc[i].insert(n + 1);

    }

    for(int i = 1; i <= k; ++i) {

        int r, c;

        scanf("%d%d", &r, &c);

        sr[r].insert(c);

        sc[c].insert(r);

    }

    int u = 1, d = n, l = 1, r = m;

    int x = 1, y = 1, dir = 1, stay = 0;

    ll cnt = 1;

    while(d >= u && r >= l) {

        if(dir == 1) {///行向右

            int ny = min(r, *sr[x].upper_bound(y) - 1);///r是蛇不断走的时候的边界，例如我们第一开始在第一行撞到了阻碍物，那么我们只能右转对吧，那此刻的r边界在下面就更新了，下一次在行里面就不能靠阻碍物位置了而是自己的以该r为边界，因为一个格子不能重复两次

            cnt += ny - y;

            if(ny == y) {

                if(stay == 0)

                    stay = 1;

                else

                    break;

            } else

                stay = 0;///如果出现原地踏步两次直接break；

            y = ny;                                                   //^

            ++u;//上边界+1，因为该行--------->已经被通过一次了，我们下次|上来的时候是不能碰到这一行的

                                                                    //  |

            r = y;

            dir = 2;

        }

        else if(dir == 2) {///列向下

            int nx = min(d, *sc[y].upper_bound(x) - 1);

            cnt += nx - x;

            if(nx == x) {

                if(stay == 0)

                    stay = 1;

                else

                    break;

            } else

                stay = 0;

            x = nx;

            --r;

            d = x;

            dir = 3;

        } else if(dir == 3) {///行向左

            int ny = max(l, *(--(sr[x].lower_bound(y))) + 1);

            cnt += y - ny;

            if(ny == y) {

                if(stay == 0)

                    stay = 1;

                else

                    break;

            } else

                stay = 0;

            y = ny;

            --d;

            l = y;

            dir = 4;

        } else {///列向上

            int nx = max(u, *(--(sc[y].lower_bound(x))) + 1);

            cnt += x - nx;

            if(nx == x) {

                if(stay == 0)

                    stay = 1;

                else

                    break;

            } else

                stay = 0;

            x = nx;

            ++l;

            u = x;

            dir = 1;

        }

    }

    puts((cnt == 1ll * n * m - k) ? "YES" : "NO");

}

巴特西

cf 模拟

最新文章

热门文章