Codeforces 1064D Labyrinth（双向队列，BFS）

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 ≤ 10^9) — 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

4 5
3 2
1 2
.....
.***.
...**
*....

Output

10

Input

4 4
2 2
0 1
....
..*.
....
....

Output

7

 

Note

Cells, reachable in the corresponding example, are marked with '+'.

First example:

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

Second example:

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

 

题意：给你一个n*m的地图，然后让你从一个起点开始走，上下走没限制，但是对左右有限制，求所有能到达的点的数量。

解题方法：

如果我们的bfs先走的是上面的那条路的话，那么就会输出错误的答案（可以手模一下）。原因是我们给某些关键点打上标记时，剩余的向左走和向右走的次数也许不是最多的，这样会导致有些格子无法访问（但是这样竟然能过Pretest）。
于是我们改变一下搜索的顺序：用双端队列，向上走或向下走时就push到队头，向左走或向右走时就push到队尾（其实就是先处理一列）。这样我们就能保证给某个格子打上标记时，当前剩余的向左走和向右走的次数是最多的啦。

这是其中一组样例

10 10
10 4
10 9
...*******
.*.*******
.*.*******
.*.*******
.*.*******
.*.*......
.*.*.*****
.*........
.********.
..........

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=2e3+10;
int n,m,sx,sy,l,r;
int dx[]={-1,0,0,1};
int dy[]={0,1,-1,0};
struct Node{
	int x,y,sl,sr;
	Node(){}
	Node(int a,int b,int c,int d):x(a),y(b),sl(c),sr(d){}
};
char mp[maxn][maxn];
bool vis[maxn][maxn];
deque<Node> qu;
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&sx,&sy);
	scanf("%d%d",&l,&r);
	for(i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
	}
	int ans=1;
	vis[sx][sy]=true;
	//while(!qu.empty()) qu.pop();
	qu.push_front(Node(sx,sy,l,r));
	while(!qu.empty()){
		Node no=qu.front();qu.pop_front();
		for(i=0;i<4;i++){
			int xx=no.x+dx[i];
			int yy=no.y+dy[i];
			if(vis[xx][yy]||xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='*') continue;
			if(i==1){
				if(no.sr>=1){
					vis[xx][yy]=true;ans++;
					qu.push_back(Node(xx,yy,no.sl,no.sr-1));
				}
			}
			else if(i==2){
				if(no.sl>=1){
					vis[xx][yy]=true;ans++;
					qu.push_back(Node(xx,yy,no.sl-1,no.sr));
				}
			} 
			else{
				vis[xx][yy]=true;ans++;
				qu.push_front(Node(xx,yy,no.sl,no.sr));
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

 

还有一种解题方法：我用往左边走的次数来更新从起点到当前点的距离，然后我跑完最短路后，暴力更新答案就行。

双向队列还是很好用的。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const int maxn=2e3+10;
int n,m,sx,sy,l,r;
int dx[]={-1,0,0,1};
int dy[]={0,1,-1,0};
struct Node{
	int x,y;
	Node(){}
	Node(int a,int b):x(a),y(b){}
};
int dis[maxn][maxn];
bool vis[maxn][maxn];
char mp[maxn][maxn];
deque<Node> qu;
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&sx,&sy);
	scanf("%d%d",&l,&r);
	for(i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
	}
	mem(vis,0);mem(dis,inf);
	int ans=0;
	vis[sx][sy]=1;dis[sx][sy]=0;
	//while(!qu.empty()) qu.pop();
	qu.push_front(Node(sx,sy));
	while(!qu.empty()){
		Node no=qu.front();qu.pop_front();vis[no.x][no.y]=0;
		for(i=0;i<4;i++){
			int xx=no.x+dx[i];
			int yy=no.y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy]=='*') continue;
			if(i==2){
				if(dis[xx][yy]>dis[no.x][no.y]+1){
					dis[xx][yy]=dis[no.x][no.y]+1;
					if(!vis[xx][yy]){
						vis[xx][yy]=1;
						qu.push_back(Node(xx,yy));
					}
				}
			}
			else{
				if(dis[xx][yy]>dis[no.x][no.y]){
					dis[xx][yy]=dis[no.x][no.y];
					if(!vis[xx][yy]){
						vis[xx][yy]=1;
						qu.push_front(Node(xx,yy));
					}
				}
			} 
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			//printf("%d ",dis[i][j]);
			if(dis[i][j]<=l&&(j-sy+dis[i][j])<=r){
				//printf("%d %d\n",i,j);
				ans++;
			} 
		}
		//printf("\n");
	}
	printf("%d\n",ans);
	return 0;
}