本文主要是介绍ICPC-搜索-CF516DIV2-1064D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个数据结构用的相当巧妙
题目
http://codeforces.com/contest/1064/problem/D
给你n,m表行列数
x,y是起点位置
L，R是你能向左走的数量和向右走的数量（向上向下无限制）
给你相关地图，求从起点能到达的格子数
思路
一开始就想到BFS。但是WA test40
然后看了大佬的解法，感觉世界都亮了。
因为我没考虑一件事，上下和左右，应该优先拿上下的，这样可以使得所有格子都是最短路径到达。
所以：deque出场了，双端队列，自己了解一下啦。
代码
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))//不能mem(double)
#define ll long long
const double eps=3e-8;
const int mod=10;
const int maxn=10005;
int sum=0;
struct node{int x,y,rx,ry;node(int xx,int yy,int l,int r):x(xx),y(yy),rx(l),ry(r){}node(){}
};
char a[2010][2010];
bool vis[2010][2010];
int n,m;
int sx,sy,L,R;
deque<node>q;
int bfs(int xx,int yy){q.clear();mem(vis,0);q.push_back(node(xx,yy,L,R));while(!q.empty()){node tmp=q.front();q.pop_front();int x=tmp.x;int y=tmp.y;if(vis[x][y])continue;//cout<<"num:"<<sum<<" xy="<<x<<" "<<y<<endl;vis[x][y]=1;sum++;if(x>1&&a[x-1][y]=='.') q.push_front(node(x-1, y, tmp.rx, tmp.ry));//upif(x<n&&a[x+1][y]=='.') q.push_front(node(x+1, y, tmp.rx, tmp.ry));//downif(y>1&&a[x][y-1]=='.'&&tmp.rx) q.push_back(node(x, y-1, tmp.rx-1, tmp.ry));//leftif(y<m&&a[x][y+1]=='.'&&tmp.ry) q.push_back(node(x, y+1, tmp.rx, tmp.ry-1));//right}return sum;
}
int main(){cin>>n>>m;cin>>sx>>sy;cin>>L>>R;for(int i=1;i<=n;i++){scanf("%s",a[i]+1);//快很多}cout<<bfs(sx,sy)<<endl;return 0;
}
中间输出看看
这篇关于ICPC-搜索-CF516DIV2-1064D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
