题目连接：http://codeforces.com/contest/1064/problem/D
题意是有一个n*m的地图，然后输入一个坐标为起点，第三行为l和r，表示只能向左移动l次，向右移动r次，上下移动是没有限制的，'*'是不可走的，问最多能到达多少个点。
思路是用双端队列来实现，因为上下走是没有限制的，所以我们可以优先去走上下，尽量把向左向右走的情况往后放，这样搜才能保证是最优的，因此我们可以用双端队列来实现这个队列的顺序，当我们上下走的时候，就把这个点push到前面，如果要左右走的话就push到队尾，然后我们正着去取队首元素，就可以达到先上下后左右的目的了，做法就是讨论四个方向的情况就好了，这道题好像也能用最短路做...有时间补一下吧...
AC代码：
代码语言：javascript复制#include <bits/stdc .h>
#define maxn 2005
using namespace std;
struct Node{
int x,y,l,r;
Node (int x,int y,int l,int r) : x(x), y(y), l(l), r(r) {}
};
int n,m;
bool vis[maxn][maxn];
char MAP[maxn][maxn];
int ans;
int Sx,Sy,Sl,Sr;
void bfs(){
Node S = Node(Sx, Sy, Sl, Sr);
deque<Node> q;
memset(vis,false,sizeof(vis));
ans = 0;
q.push_front(S);
while(!q.empty()){
Node Now = q.front();
q.pop_front();
int xx = Now.x, yy = Now.y, l = Now.l, r = Now.r;
if(vis[xx][yy]) continue;
vis[xx][yy] = true;
ans ;
if(xx - 1 >= 0 && MAP[xx - 1][yy] != '*')
q.push_front(Node(xx - 1, yy, l, r));
if(xx 1 < n && MAP[xx 1][yy] != '*')
q.push_front(Node(xx 1, yy, l, r));
if(yy - 1 >= 0 && MAP[xx][yy - 1] != '*' && l)
q.push_back(Node(xx, yy - 1, l - 1, r));
if(yy 1 < m && MAP[xx][yy 1] != '*' && r)
q.push_back(Node(xx, yy 1, l, r - 1));
}
printf("%dn",ans);
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&Sx,&Sy,&Sl,&Sr);
Sx --; Sy --;
for(int i=0;i<n;i ){
scanf("%s",MAP[i]);
}
bfs();
return 0;
}
