AcWing 4481. 方格探索
原题链接
困难
作者:
小.bug
,
2022-06-12 10:49:31
,
所有人可见
,
阅读 273
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 2010;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};
char g[N][N];
int n, m, sx, sy, ml, mr;
int d[N][N];
bool st[N][N];
void bfs()
{
memset(d, 0x3f, sizeof d);
deque<pii> q;
q.push_back({sx,sy});
d[sx][sy] = 0;
while(q.size())
{
pii t = q.front();
q.pop_front();
int x = t.x, y = t.y;
if(st[x][y]) continue;
st[x][y] = true;
for(int k = 0; k < 4; k++)
{
int nx = x + dx[k], ny = y + dy[k];
int w = 0;
if(k == 3) w = 1;
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '.')
{
if(d[nx][ny] > d[x][y] + w)
{
d[nx][ny] = d[x][y] + w;
if(w) q.push_back({nx,ny});
else q.push_front({nx,ny});
}
}
}
}
}
int main()
{
cin >> n >> m;
cin >> sx >> sy;
cin >> ml >> mr;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> g[i][j];
}
}
bfs();
int cnt = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(d[i][j] <= mr && (d[i][j] - (j - sy)) <= ml) cnt ++;
}
}
cout << cnt << endl;
return 0;
}