题目翻译
给你一个\(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;
}