题意：
给出一个方格，('.') 表示可以行走，('*') 表示障碍。给出一个出发点 ((r,c))，向左和向右走的次数限制分别为：(x,y) 次。问从出发点出发，可以到达几个点。
分析：
由于有向左和向右走的限制，因此每次走的时候应该考虑如何使得向左和向右走的次数最少。而不是直接用 (bfs)，走的步数和向左和向右的次数没有必然关系。
解法 (1)：
把走到每个位置的花费的向左和向右走的次数记录下来，一个点可能走多次，如果一个点有更少的次数，就更新，从这个点再走一次。
解法 (2)：
用一个双端队列，如果该点是从下或向上走得到的点就从前面入队，否则就从后面入队。这样可以保证队列前面的点向左和向右走的次数更少。
解法 (3)：
如果我们保证了到达一个点时向左走的次数最少，那么就可以保证向右走的次数最少。因为向右走了一次之后肯定需要向左走一次来抵消掉这次操作。把向左/右的边权看成 (1)，向上/下的边权看成 (0)，然后 (01bfs)。
代码同解法 (2)。
代码：
代码 (1)：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
const int N=2010;
char pic[N][N];
bool vis[N][N];
P num[N][N];
int n,m,r,c,nx,ny,cnt;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
struct node
{
int x,y,ln,rn;
};
queue<node>que;
bool check(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&pic[x][y]=='.')
return 1;
return 0;
}
void bfs()
{
while(!que.empty())
que.pop();
que.push(node{r,c,0,0});
cnt=1;
vis[r][c]=1;
num[r][c]=make_pair(0,0);
while(!que.empty())
{
node now=que.front();
que.pop();
for(int i=0;i<4;i++)
{
int tx=now.x+dx[i];
int ty=now.y+dy[i];
if(check(tx,ty))
{
int t1=now.ln+(i==1);
int t2=now.rn+(i==3);
if((!vis[tx][ty]||vis[tx][ty]&&(num[tx][ty].first>t1||num[tx][ty].second>t2))&&t1<=nx&&t2<=ny)
{
if(!vis[tx][ty])
cnt++;
que.push(node{tx,ty,t1,t2});
vis[tx][ty]=1;
num[tx][ty]=make_pair(t1,t2);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d",&r,&c);
scanf("%d%d",&nx,&ny);
for(int i=1;i<=n;i++)
scanf("%s",pic[i]+1);
bfs();
printf("%d
",cnt);
return 0;
}
代码 (2)：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y,ln,rn;
};
deque<node>dq;
const int N=2010;
int n,m,r,c,nx,ny,cnt;
char pic[N][N];
bool vis[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool check(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&pic[x][y]=='.'&&!vis[x][y])
return 1;
return 0;
}
void bfs()
{
cnt=1;
while(!dq.empty())
dq.pop_back();
dq.push_front(node{r,c,0,0});
vis[r][c]=1;
while(!dq.empty())
{
node now=dq.front();
dq.pop_front();
for(int i=0;i<4;i++)
{
int tx=now.x+dx[i];
int ty=now.y+dy[i];
if(!check(tx,ty))
continue;
if(i<=1)
{
cnt++;
dq.push_front(node{tx,ty,now.ln,now.rn});
vis[tx][ty]=1;
}
else
{
int t1=now.ln+(i==2);
int t2=now.rn+(i==3);
if(t1<=nx&&t2<=ny)
{
cnt++;
dq.push_back(node{tx,ty,t1,t2});
vis[tx][ty]=1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d",&r,&c);
scanf("%d%d",&nx,&ny);
for(int i=1;i<=n;i++)
scanf("%s",pic[i]+1);
bfs();
printf("%d
",cnt);
return 0;
}