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:

.++.
.+*.
.++.
.++.

 
1. 원제 주소
점아 전송
 
대체로
sx,sy에서 시작하는 n*m 행렬을 보여 줍니다.L과 R을 제시하면 이동하는 과정에서 최대 왼쪽으로 L회, 최대 오른쪽으로 R회만 갈 수 있음을 나타낸다.시작점(sx,sy)부터 도달할 수 있는 점의 개수를 묻습니다.이 수를 출력하다.
 
3. 사고방식
일반적인 BFS용vis는 4차원vis를 사용하지 않는 한 현재 상태를 저장할 수 없다.일반적인 BFS에서 해결할 수 없는 것은 걸음수는 적지만 커브 횟수가 많은 경우이다. 이런 걸음걸이는 길이가 짧지만 커브 횟수가 많기 때문에 뒤의 걸음걸이를 제한한다. 그러나 그는vis에게 미리 표시를 해서 걸음수는 많지만 커브 횟수가 적은 상태는 갱신할 수 없다.
그래서 우선 대기열을 사용해서 횟수가 적은 상태점을 미리 업데이트합니다.이렇게 하면 위에서 말한 잘못된 상황이 발생하지 않도록 보장할 수 있다.
 
4. 코드

#include
#include
#include
#include
#include
#include
#include
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  a.tol + a.tor;
	}
};
int BFS()
{
	int ret = 1;
	memset(vis, false, sizeof(vis));
	vis[sx][sy] = true;
	priority_queueq;
	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
", BFS());
	getchar();
	getchar();
}