https://codeforces.com/contest/1064/problem/D
题意
给你一个有障碍的图，限制你向左向右走的次数，问你可以到达格子的个数
思路
- 可以定义状态为vi[x][y][l][r]，状态唯一，理论上可以bfs或者dfs都可以搜出唯一结果，但是时间空间复杂度都不允许
- 进而要不改变状态定义或者找找规律或者思考贪心（调整访问顺序）在做这道题之前并不知道便利顺序对于搜索有这么大的影响
- 我尝试了重新定义状态为vi[x][y][dir]，但是用了dfs还是wa
- 根本问题是，先访问（标记）的点后面就不能访问了，可以定义多一维状态或者按照某种顺序访问点，因此贪心原则是：同样能到达一个点，但是剩下向左向右次数越多，就能走得更远，因此优先访问上下的点，在访问左右的点。
关于搜索
搜索现阶段来说已经不再是套板子了，而是需要根据实际用途进行调整
- dfs or bfs
- dfs走到没有路为止，在这道题里面返回边界是四周都不能走or左右步数用完，能够反悔
- bfs走一步向四周拓展一步，访问一个状态有先后顺序，并不能反悔
- 在这道题中，因为优先走上下，然后走左右，dfs需要便利本层所有方向才返回，所以并不能满足先走上下，再走左右。bfs可以实现。
- bfs用什么容器
- 根据实际情况，本题需要先访问上下的点，再访问左右的点，因此这题可以用一个双端队列，上下走的放在队头，左右走的放在队尾，每次取队首元素
- 遍历的顺序
- 标记下一个点 or 标记当前访问的点
- bfs一定要标记下一个点，防止重复入队
- dfs标记下一个点，可以抹掉（用于反悔）。标记当前点不可以抹掉
- 标记的状态是否唯一
#include<bits/stdc++.h>
using namespace std;
struct N{
int x,y,l,r;
};
int vi[2005][2005];
char g[2005][2005];
int n,m,stx,sty,L,R,ans,i,j;
deque<N>q;
void bfs(){
q.push_front(N{stx,sty,0,0});
ans=0;
vi[stx][sty]=1;
while(!q.empty()){
N u=q.front();q.pop_front();
int x=u.x,y=u.y,l=u.l,r=u.r;
ans++;
if(x-1>0&&!vi[x-1][y]){
q.push_front(N{x-1,y,l,r});
vi[x-1][y]=1;
}
if(x+1<=n&&!vi[x+1][y]){
q.push_front(N{x+1,y,l,r});
vi[x+1][y]=1;
}
if(y-1>0&&!vi[x][y-1]&&l<L){
q.push_back(N{x,y-1,l+1,r});
vi[x][y-1]=1;
}
if(y+1<=m&&!vi[x][y+1]&&r<R){
q.push_back(N{x,y+1,l,r+1});
vi[x][y+1]=1;
}
}
}
int main(){
cin>>n>>m>>stx>>sty>>L>>R;
for(i=1;i<=n;i++){
scanf("%s",g[i]+1);
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
if(g[i][j]=='*')vi[i][j]=1;
bfs();
cout<<ans;
}