Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) D. Labyrinth （BFS+特殊处理）

题目链接：http://codeforces.com/problemset/problem/1063/B

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 ≤ 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的迷宫，'.'表示没有障碍，'*'表示有障碍。现在你从第r行第c列出发，上下可以无限走，向左最多走x步，向右最多走y步。问最多能访问多少个点？

分析：如果没有左右步数的限制，那么这个题可以用裸的bfs解决。现在左右加上了步数限制，我们可以考虑给每个点做个标记，标记的内容为到达这个点时向左走的步数最大是多少和到达这个点时向右走的步数最大是多少，这样，从一个点向上下左右四个点走时，一是访问那些没有访问过同时可以走的点，二是虽然之前访问过，但是从现在这个点出发的话能使剩余的向左走或向右走的步数尽可能大，并保留向左或向右的最大值（向左走和向右走之间不相互影响）。这样每个点第一次访问时进行计数即可。

看网上有用优先队列和双端队列实现的，思路上更清晰一些。

AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 2005;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
char mp[maxn][maxn];
int zuo[maxn][maxn],you[maxn][maxn];
bool vis[maxn][maxn];
int cnt,n,m,r,c,x,y;
struct Node
{
    int x,y;
    Node(){}
    Node(int x,int y):x(x),y(y) {}
};
queue<Node> qu;
bool isOk(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='*') return true;
    return false;
}
void tonext(int zx,int zy,int i)
{
    int tx=zx+dx[i],ty=zy+dy[i];
    int flagz = (dy[i]==-1); //如果是向左走此标记为1
    int flagy = (dy[i]==1);  //如果是向右走此标记为1
    if(!vis[tx][ty]||zuo[tx][ty]<zuo[zx][zy]-flagz||you[tx][ty]<you[zx][zy]-flagy)
    {//访问：1、之前未访问过 
     //      2、之前虽然访问过，但是从现在的点出发访问时向左的剩余步数更大 
     //      3、之前虽然访问过，但是从现在的点出发访问时向右的剩余步数更大
        if(!vis[tx][ty])
        {//如果未访问过，计数，否则只是更新剩余步数，不计数
            vis[tx][ty]=1;
            cnt++;
            //mp[tx][ty]='+';  //调试用
        }
        zuo[tx][ty] = max(zuo[tx][ty],zuo[zx][zy]-flagz);
        you[tx][ty] = max(you[tx][ty],you[zx][zy]-flagy);
        qu.push(Node(tx,ty));
    }
}
void bfs(Node st)
{
    vis[st.x][st.y]=1;
    mp[st.x][st.y]='+';
    cnt++;
    qu.push(st);
    while(!qu.empty())
    {
        Node tem = qu.front();
        qu.pop();
        if(isOk(tem.x+dx[0],tem.y+dy[0])) tonext(tem.x,tem.y,0);
        if(isOk(tem.x+dx[1],tem.y+dy[1])) tonext(tem.x,tem.y,1);
        if(isOk(tem.x+dx[2],tem.y+dy[2])&&you[tem.x][tem.y]>=1) tonext(tem.x,tem.y,2);
        if(isOk(tem.x+dx[3],tem.y+dy[3])&&zuo[tem.x][tem.y]>=1) tonext(tem.x,tem.y,3);
    }
}
int main()
{
    cnt=0;
    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
    for(int i = 1; i <= n; ++i)
        scanf("%s",mp[i]+1);
    for(int i = 0; i <= m; ++i) mp[0][i] = mp[n+1][i] = '.';
    for(int i = 0; i <= n; ++i) mp[i][0] = mp[i][m+1] = '.';
    for(int i = 0; i <= n+1; ++i)
        for(int j = 0; j <= m+1; ++j) zuo[i][j]=you[i][j]=vis[i][j]=0;
    zuo[r][c]=x;
    you[r][c]=y;
    bfs(Node(r,c));
    printf("%d\n",cnt);
    //for(int i = 1;i <= n; ++i)
    //{
    //    for(int j = 1; j <= m; ++j)
    //        printf("%c",mp[i][j]);
    //    printf("\n");
    //}
    return 0;
}