欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 1064D/1063B Labyrinth

程序员文章站 2022-05-10 09:10:36
...

原题链接/原题链接(代理站)

题目翻译

给你一个\(n*m\)的迷宫和起始点,有障碍的地方不能走,同时最多向左走\(x\)次,向右走\(y\)次,向上向下没有限制,问你有多少个格子是可以到达的。

输入样例

4 5
3 2
1 2
.....
.***.
...**
*....

输出样例

10

数据范围

\(n,m\leqslant 2000\)

考虑最裸的\(bfs\),开一个队列,从起点开始,每搜到一个格子就打上标记。但是这样显然是错的,考虑下面这组数据:

.....
.***.
...*.
*.**.
*.**.
*....

这是一个\(6*5\)的网格,起始点为\((1,5)\),最多向左走\(5\)次,向右走\(1\)次。
如果我们的\(bfs\)先走的是上面的那条路的话,那么就会输出错误的答案(可以手模一下)。原因是我们给某些关键点打上标记时,剩余的向左走和向右走的次数也许不是最多的,这样会导致有些格子无法访问(但是这样竟然能过Pretest)。
于是我们改变一下搜索的顺序:用双端队列,向上走或向下走时就\(push\)到队头,向左走或向右走时就\(push\)到队尾(其实就是先处理一列)。这样我们就能保证给某个格子打上标记时,当前剩余的向左走和向右走的次数是最多的啦。
代码:

#include <bits/stdc++.h>

using namespace std;

#define N 2000

int n, m, r, c, pp, qq, vis[N+5][N+5], ans;
char a[N+5][N+5];

struct S {
    int x, y, le, ri;
};

void bfs() {
    deque<S> q;
    q.push_front(S{r, c, pp, qq});
    vis[r][c] = 1;
    int nx, ny;
    while(!q.empty()) {
        S u = q.front(); q.pop_front();
        nx = u.x+1, ny = u.y;
        if(nx <= n && !vis[nx][ny] && a[nx][ny] == '.') {
            vis[nx][ny] = 1;
            q.push_front(S{nx, ny, u.le, u.ri});
        }
        nx = u.x-1, ny = u.y;
        if(nx >= 1 && !vis[nx][ny] && a[nx][ny] == '.') {
            vis[nx][ny] = 1;
            q.push_front(S{nx, ny, u.le, u.ri});
        }
        nx = u.x, ny = u.y-1;
        if(ny >= 1 && !vis[nx][ny] && u.le >= 1 && a[nx][ny] == '.') {
            vis[nx][ny] = 1;
            q.push_back(S{nx, ny, u.le-1, u.ri});
        }
        nx = u.x, ny = u.y+1;
        if(ny <= m && !vis[nx][ny] && u.ri >= 1 && a[nx][ny] == '.') {
            vis[nx][ny] = 1;
            q.push_back(S{nx, ny, u.le, u.ri-1});
        }
    }
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &r, &c, &pp, &qq);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) cin >> a[i][j];
    bfs();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) ans += vis[i][j];
    cout << ans << endl;
    return 0;
}