codeforces 1063B. Labyrinth 【01bfs】

题目大意：在一个地图上，有些点不能走，有些点可以走，向左走向右走会有花费，向上和向下没有，现在给定起点，和向左走、向右走的最多步数，问能够走到的点有多少个

题目分析：这个题如果直接bfs 去搜的话，没有办法很好的更新到达某个点最少需要多少个向左走，所以我们用bfs跑一个最短路，dist[i][j] 表示达到 （i,j）这个点最少需要向左走的步数，那么向右走的步数就为 j-c0+dist[i][j] (其中 c0 表示起点的纵坐标)

这样我们就可以算出来最远可以达到的距离了
提醒：千万要注意 ，关闭同步之后，不要 cin，cout 和scanf一起用

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int maxn=5005+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
//head
int n=0,m=0,r=0,c=0,x=0,y=0;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int cost[]={1,0,0,0};
char board[maxn][maxn];
int dist[maxn][maxn];
struct node
{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
};
void bfs(int s,int t)
{
   deque<node>q;
   node te;
   dist[s][t]=0;
   te.x=s; te.y=t;
   q.push_back(te);
   while(!q.empty())
   {
       node tmp = q.front();
       q.pop_front();
       for(int i=0;i<4;i++)
       {
           int tx = tmp.x+dx[i];
           int ty = tmp.y+dy[i];
           int tc = cost[i];
           if(tx<0||tx>=n)continue;
           if(ty<0||ty>=m)continue;
           if(board[tx][ty]=='*') continue;
           if(dist[tx][ty]>dist[tmp.x][tmp.y]+tc)
           {
               dist[tx][ty]=dist[tmp.x][tmp.y]+tc;
               if(tc)
               {
                   q.push_back(node(tx,ty));
               }
               else q.push_front(node(tx,ty));
           }
       }
   }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    cin>>r>>c;
    cin>>x>>y;
    for(int i=0;i<n;i++)
    {
        cin>>board[i];

    }
    memset(dist,inf,sizeof(dist));
    int ans =0;
    r--,c--;
    bfs(r,c);
   // rep(i,0,n) {rep(j,0,m) cout<<dist[i][j]<< " ";cout<<endl;}

    rep(i,0,n)
    {
        rep(j,0,m)
        {
            if(dist[i][j]>1e8) continue;
            int left = dist[i][j];
            int right = 0;
            right = j-(c-left);
            ans +=(right<=y&&left<=x)?1:0;
        }
    }
    cout<<ans<<"\n";

    return 0;
}