Codeforces Round #516 Div.2 D. Labyrinth(双端队列)

Ch_Zaqdt

发布于 2019-01-11 10:58:43

4450

发布于 2019-01-11 10:58:43

文章被收录于专栏：Zaqdt_ACM

题目连接：http://codeforces.com/contest/1064/problem/D

题意是有一个n*m的地图，然后输入一个坐标为起点，第三行为l和r，表示只能向左移动l次，向右移动r次，上下移动是没有限制的，'*'是不可走的，问最多能到达多少个点。

思路是用双端队列来实现，因为上下走是没有限制的，所以我们可以优先去走上下，尽量把向左向右走的情况往后放，这样搜才能保证是最优的，因此我们可以用双端队列来实现这个队列的顺序，当我们上下走的时候，就把这个点push到前面，如果要左右走的话就push到队尾，然后我们正着去取队首元素，就可以达到先上下后左右的目的了，做法就是讨论四个方向的情况就好了，这道题好像也能用最短路做...有时间补一下吧...

AC代码：

#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("%d\n",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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年10月16日，如有侵权请联系 cloudcommunity@tencent.com 删除

push