对于位置(i,j), j - c = R - L = const(常数), 其中R表示往右走了几步,L表示往左走了几步
所以R越大, L就越大, R越小, L就越小, 所以只需要最小化L和R中的其中一个就可以了
由于每次变化为0或1,所以用双端队列写bfs, 保证最前面的值最小, 简化版的dijkstra
不过看到好多没写双端队列的也过了......
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 2e3 + 5; char s[N][N]; int mnr[N][N]; int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; deque<piii> q; int n, m; void bfs(int x, int y, int rx, int ry) { mem(mnr, 0x3f); mnr[x][y] = 0; q.push_back({{x, y}, 0}); while(!q.empty()) { piii p = q.front(); q.pop_front(); for (int i = 0; i < 4; i++) { int xx = p.fi.fi + dir[i][0]; int yy = p.fi.se + dir[i][1]; if(i == 1) { if(1 <= xx && xx <= n && 1 <= yy && yy <= m && s[xx][yy] == '.' && p.se + 1 < mnr[xx][yy]) { mnr[xx][yy] = p.se+1; q.push_back({{xx, yy}, p.se+1}); } } else { if(1 <= xx && xx <= n && 1 <= yy && yy <= m && s[xx][yy] == '.' && p.se < mnr[xx][yy]) { mnr[xx][yy] = p.se; q.push_front({{xx, yy}, p.se}); } } } } } int main() { int r, c, x, y; scanf("%d %d", &n, &m); scanf("%d %d", &r, &c); scanf("%d %d", &x, &y); for (int i = 1; i <= n; i++) scanf("%s", s[i]+1); int ans = 0; bfs(r, c, x, y); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int cst = j - c; int l = mnr[i][j] - cst; if(mnr[i][j] <= y && l <= x) ans++; } } printf("%d ", ans); return 0; }