codeforces 1064D. Labyrinth(BFS优先队列优化)
D. Labyrinth
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
You are playing some computer game. One of its levels puts you in a maze consisting of n lines, each of which contains m cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row r and column c. In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can't move beyond the boundaries of the labyrinth.
Unfortunately, your keyboard is about to break, so you can move left no more than x times and move right no more than y times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.
Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 2000) — the number of rows and the number columns in the labyrinth respectively.
The second line contains two integers r, c (1 ≤ r ≤ n, 1 ≤ c ≤ m) — index of the row and index of the column that define the starting cell.
The third line contains two integers x, y (0 ≤ x, y ≤ 109) — the maximum allowed number of movements to the left and to the right respectively.
The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols '.' and '*'. The j-th character of the i-th line corresponds to the cell of labyrinth at row i and column j. Symbol '.' denotes the free cell, while symbol '*' denotes the cell with an obstacle.
It is guaranteed, that the starting cell contains no obstacles.
Output
Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.
Examples
input
Copy
4 5
3 2
1 2
.....
.***.
...**
*....
output
Copy
10
input
Copy
4 4
2 2
0 1
....
..*.
....
....
output
Copy
7
Note
Cells, reachable in the corresponding example, are marked with '+'.
First example:
+++..
+***.
+++**
*+++.
Second example:
.++.
.+*.
.++.
.++.
一、原题地址
二、大致题意
给出一个n*m的矩阵，起点在sx,sy。给出一个L和一个R，表示在移动的过程中最多只能向左走L次，最多向右走R次。询问从起点(sx,sy)开始所能到达的点的个数。输出这个数。
三、思路
一般的BFS用vis是保存不了当前的状态的，除非使用四维的vis。而一般的BFS不能解决的是那些步数少但是拐弯次数多的情况，这种走法路程短但是拐弯次数多，所以会限制后面的走法，但是他会提前给vis打上标记，导致那些虽然步数多但是拐弯次数少的状态无法更新。
所以这里用优先队列，将次数少的状态点提前更新。这样可以保证上面所说的错误情况不发生。
四、代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int sx, sy;
int L, R;
char mmp[2005][2005];
bool vis[2005][2005];
int x[] = { 1,-1,0,0 };
int y[] = { 0,0,1,-1 };
struct Node
{
int x, y;
int tol, tor;
bool operator <(Node a)const
{
return tol + tor > a.tol + a.tor;
}
};
int BFS()
{
int ret = 1;
memset(vis, false, sizeof(vis));
vis[sx][sy] = true;
priority_queue<Node>q;
Node st; st.x = sx, st.y = sy;
st.tol = 0, st.tor = 0;
q.push(st);
while (!q.empty())
{
Node t = q.top();
q.pop();
for (int i = 0; i < 4; i++)
{
int xx = t.x + x[i], yy = t.y + y[i];
if (xx >= 1 && xx <= n&&yy >= 1 && yy <= m&&yy >= sy - L&&yy <= sy + R&&mmp[xx][yy] != '*')
{
if (i == 2)
{
if (!vis[xx][yy] && t.tor + 1 <= R)
{
ret++;
Node nex;
nex.x = xx, nex.y = yy;
nex.tol = t.tol, nex.tor = t.tor + 1;
q.push(nex);
vis[xx][yy] = true;
}
}
else if (i == 3)
{
if (!vis[xx][yy] && t.tol + 1 <= L)
{
ret++;
Node nex;
nex.x = xx, nex.y = yy;
nex.tol = t.tol + 1, nex.tor = t.tor;
q.push(nex);
vis[xx][yy] = true;
}
}
else
{
if (!vis[xx][yy])
{
ret++;
Node nex;
nex.x = xx, nex.y = yy;
nex.tol = t.tol, nex.tor = t.tor;
q.push(nex);
vis[xx][yy] = true;
}
}
}
}
}
return ret;
}
void read()
{
scanf("%d %d", &n, &m);
scanf("%d %d", &sx, &sy);
scanf("%d %d", &L, &R);
getchar();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%c", &mmp[i][j]);
}
getchar();
}
}
int main()
{
read();
printf("%d\n", BFS());
getchar();
getchar();
}