直接给出中文题意
链接：https://ac.nowcoder.com/acm/contest/332/J
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
你在一个 n 行 m 列的网格迷宫中，迷宫的每一格要么为空，要么有一个障碍。
你当前在第 r 行第 c 列(保证该格子为空)。每次移动你可以向上下左右任意一个方向移动一格，前提是不能走到障碍上，也不能超出迷宫的边界。
你向左移动的次数不能超过 x 次，向右不能超过 y 次。
问在这种情况下，对于每个格子，是否存在一种移动方案让你走到它。
输出有多少个格子存在移动方案让你走到它。
输入描述:
第一行两个正整数 n,m 。 第二行两个正整数 r,c ，保证 1≤r≤n1≤r≤n ，1≤c≤m1≤c≤m 。 第三行两个整数 x,y ，保证 0≤x,y≤1090≤x,y≤109 。 接下来 n 行，每行一个长度为 m 的字符串， 第 i 行第 j 个字符表示迷宫第 i 行第 j 列的格子， 字符为`.` 表示格子为空，字符为`*` 表示格子上有一个障碍。
输出描述:
输出一个数，表示有多少个格子存在移动方案让你走到它。
示例1
输入
复制
4 5 3 2 1 2 ..... .***. ...** *....
输出
复制
10
说明
将能走到的格子用+标记：+++.. +***. +++** *+++.
示例2
输入
复制
4 4 2 2 0 1 .... ..*. .... ....
输出
复制
7
说明
.++. .+*. .++. .++.
备注:
对于全部数据， 1≤n,m≤10001≤n,m≤1000 。
分析：
牛客网数据太水了，普通的bfs就能过，但在CF上就过不了。
本题给出的限制为上下可以无限走，但左右有步数限制，一般的BFS只能找到最快的路劲，但是对于这题不是最优的，我们这题最优的是：向左走的步数+向右走的步数最少的先走。所以改一下队列的优先性质即可。
双端队列的做法：
优先队列做法：
import java.io.BufferedInputStream;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {static int [] dx={1,0,-1,0};static int [] dy={0,1,0,-1};static int n,m,x,y;static String[] map =new String[2005];static int[][] vis =new int[2005][2005];public static int bfs(int x1,int y1){Comparator<node> cmp;///可以new一个重载器;cmp = new Comparator<node>(){public int compare(node e1,node e2){return (e1.ls+e1.rs) - (e2.ls+e2.rs);///重载优先级}};Queue<node> q=new PriorityQueue<node>(cmp);node a = new node(x1,y1,0,0);q.offer(a);int ans=1;vis[x1][y1]=1;while(q.size()!=0){a=q.poll();//System.out.println(a);for(int i=0;i<4;i++){node b=null;if(i==1){b=new node(a.x+dx[i],a.y+dy[i],a.ls,a.rs+1);}else if(i==3)b=new node(a.x+dx[i],a.y+dy[i],a.ls+1,a.rs);else b=new node(a.x+dx[i],a.y+dy[i],a.ls,a.rs);if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&map[b.x].charAt(b.y)!='*'&&b.ls<=x&&b.rs<=y&&vis[b.x][b.y]==0){ans++; q.offer(b);vis[b.x][b.y]=1;}}}return ans;}public static void main(String[] args) {//Scanner in = new Scanner (new BufferedInputStream(System.in));Scanner in = new Scanner(new BufferedInputStream(System.in));n=in.nextInt();m=in.nextInt();int r=in.nextInt();int c=in.nextInt();r--;c--;x=in.nextInt();y=in.nextInt();in.nextLine();for(int i=0;i<n;i++){map[i]=new String();map[i]=in.next();} int ans=bfs(r,c);System.out.println(ans);}
}
class node
{int x,y,ls,rs;public node(int x, int y, int ls, int rs) {super();this.x = x;this.y = y;this.ls = ls;this.rs = rs;
}}
双端队列
#include<bits/stdc++.h>
using namespace std;#define rep(i,l,r) for(int i=l;i<=r;++i)const int N=2000+5,inf=1e9;
char s[N][N];
int g[N][N];
deque<int>q;
int n,m,r,c;void bfs()
{rep(i,1,n)rep(j,1,m)g[i][j]=inf;g[r][c]=0;q.push_back(r*N+c);while(!q.empty()){int x=q.front();q.pop_front();int y=x%N;x/=N;if(s[x-1][y]=='.'&&g[x-1][y]>g[x][y]){g[x-1][y]=g[x][y];q.push_front((x-1)*N+y);}if(s[x+1][y]=='.'&&g[x+1][y]>g[x][y]){g[x+1][y]=g[x][y];q.push_front((x+1)*N+y);}if(s[x][y-1]=='.'&&g[x][y-1]>g[x][y]+1){g[x][y-1]=g[x][y]+1;q.push_back(x*N+y-1);}if(s[x][y+1]=='.'&&g[x][y+1]>g[x][y]+1){g[x][y+1]=g[x][y]+1;q.push_back(x*N+y+1);}}
}int main()
{//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);cin>>n>>m>>r>>c;int x,y;cin>>x>>y;rep(i,1,n)scanf("%s",s[i]+1);bfs();int ans=0;rep(i,1,n)rep(j,1,m)if(g[i][j]!=inf){int a=j-c;int b=g[i][j];ans+=(b-a)/2<=x&&(b+a)/2<=y;}cout<<ans;
}