[Codeforces Round #516][Codeforces 1063B/1064D. Labyrinth]

题目链接：1063B - Labyrinth/1064D - Labyrinth

题目大意：给定一个\(n\times m\)的图，有若干个点不能走，上下走无限制，向左和向右走的次数分别被限制为\(x\)和\(y\)，给出起点并询问有多少个点能够到达。

题解：此题坑多...本弱写裸BFS，WA了一百次_(:з」∠)_

　　　考虑从点\(A\)到点\(B\)需要向左或者向右走的次数，可以发现若设向左走的次数为\(l\)，向右走的次数为\(r\)，则\(r-l\)是个定值，因此转换成最短路问题用最短路跑一遍就好了。

#include<bits/stdc++.h>

using namespace std;

#define N 2001

#define INF 1000000007

int n,m,r,c,A,B,f[N][N],ans;

struct rua{int x,y;};

struct res

{

    int a,b;

    res operator +(const res &t)const{return {a+t.a,b+t.b};}

    bool operator <(const res &t)const{return a!=t.a?a<t.a:b<t.b;}

    bool operator <=(const res &t)const{return a<=t.a && b<=t.b;}

}dis[N][N];

bool vis[N][N];

queue<rua>q;

int get()

{

    char ch=getchar();

    while(ch!='.' && ch!='*')

      ch=getchar();

    return ch=='.';

}

int main()

{

    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&A,&B);

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

        f[i][j]=get(),dis[i][j]={INF,INF};

    dis[r][c]={,};

    q.push({r,c}),vis[r][c]=true;

    while(!q.empty())

      {

      rua cur=q.front();q.pop();

      int x=cur.x,y=cur.y;

      vis[x][y]=false;

      if(x> && f[x-][y] && dis[x][y]<dis[x-][y])

        {dis[x-][y]=dis[x][y];if(!vis[x-][y])q.push({x-,y}),vis[x-][y]=true;}

      if(x<n && f[x+][y] && dis[x][y]<dis[x+][y])

        {dis[x+][y]=dis[x][y];if(!vis[x+][y])q.push({x+,y}),vis[x+][y]=true;}

      if(y> && f[x][y-] && dis[x][y]+(res){,}<dis[x][y-])

        {dis[x][y-]=dis[x][y]+(res){,};if(!vis[x][y-])q.push({x,y-}),vis[x][y-]=true;}

      if(y<m && f[x][y+] && dis[x][y]+(res){,}<dis[x][y+])

        {dis[x][y+]=dis[x][y]+(res){,};if(!vis[x][y+])q.push({x,y+}),vis[x][y+]=true;}

      }

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

        if(dis[i][j]<=res{A,B})

          ans++;

    return printf("%d\n",ans),;

}

巴特西

[Codeforces Round #516][Codeforces 1063B/1064D. Labyrinth]

最新文章

热门文章