Codeforces 1064D
题意：给定一个$n×m$的网格图，有若干个点不能走，上下走无限制，向左和向右走的次数分别被限制为$x$和$y$，给出起点并询问有多少个点能够到达。
这题刚开始写了个裸 BFS 然后 FST 了。。原因是直接 BFS 加的维限制但是不让 vis 加维会让路被堵住让能到那个点的路径不能到那个点。
本题方法：
方法1、在原基础上改。开两个数组分别记录到某个点时左右次数还剩下的最大值，然后 BFS 走时判一下大小。感觉容易 FST
方法2、在原基础上改。将队列开为优先队列，然后用 Dij 思想，使得当前枚举的点左次数剩下的最大，相等则右次数剩下的最大，这样来做就不会堵路了，代码为这种方法。
方法3、观察到本题左走次数和右走次数分开走没有关系，最后答案交起来即可。所以我们分别建两个图，一个图对于左走边权为1，右走边权为0，另一个图反之。然后跑 Dij 答案求交
方法4、观察到本题边权仅有0,1，那么可以使用 0-1 BFS，即如果当前边为 0 ，放在双端队列的front，否则为1则放在双端队列的 back，然后照样 BFS 即可。方法与3类似。
知识点：
1、BFS 状态加维，状态也要加维，否则会堵路
2、两个 if 不要乱并，特别在有 else 的情况
3、0-1 BFS 写法
4、BFS 用堆来优化枚举顺序 (Dij)
5、网格图可以连边跑最短路什么的
6、想过的可能 BUG 不要轻易放过
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
struct data {
int x, y, rmx, rmy;
operator < (const data &b) const {
if (rmx != b.rmx) return rmx < b.rmx;
return rmy < b.rmy;
}
};
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};
int n, m, r, c, x, y, vis[2005][2005];
char ma[2005][2005];
priority_queue<data > q;
int main() {
ms(vis, 0);
cin >> n >> m >> r >> c >> x >> y;
for (int i = 1; i <= n; i++) scanf("%s", ma[i] + 1);
vis[r][c] = 1, q.push((data){r, c, x, y});
while (!q.empty()) {
data p = q.top(); q.pop();
for (int i = 0; i <= 4; i++) {
if (p.rmx == 0 && dy[i] == -1) continue;
if (p.rmy == 0 && dy[i] == 1) continue;
int tx = p.x + dx[i], ty = p.y + dy[i];
if (tx > 0 && ty > 0 && tx <= n && ty <= m && ma[tx][ty] != '*' && !vis[tx][ty]) {
vis[tx][ty] = 1;
if (dy[i] == -1) q.push((data){tx, ty, p.rmx - 1, p.rmy});
else if (dy[i] == 1) q.push((data){tx, ty, p.rmx, p.rmy - 1});
else q.push((data){tx, ty, p.rmx, p.rmy});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (vis[i][j]) ans++;
//for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) printf("%d%c", vis[i][j], j == m ? '\n' : ' ');
cout << ans;
return 0;
}
