因为本人的粗心wa了一早上，写篇博客记录一下
题目CF1063Bhttps://www.luogu.com.cn/problem/CF1063B
题意描述
你正在玩一款电脑游戏。在其中一关，你位于一个 nn 行 mm 列的迷宫。每个格子要么是可以通过的空地，要么是障碍。迷宫的起点位于第 rr 行第 cc 列。你每一步可以向上、下、左、右中的一个方向移动一格，前提是那一格不是障碍。你无法越出迷宫的边界。
不幸的是，你的键盘快坏了，所以你只能向左移动不超过 xx 格，并且向右移动不超过 yy 格。因为上下键情况良好，所以对向上和向下的移动次数没有限制。
现在你想知道在满足上述条件的情况下，从起点出发，有多少格子可以到达（包括起点）？
输入输出格式
输入格式：
第一行包含两个数 n, mn,m (1 <= n, m, <= 2000)(1<=n,m,<=2000) ,表示迷宫的行数和列数。
第二行包含两个数 r,cr,c (1 <= r <= n, 1 <= c <= m)(1<=r<=n,1<=c<=m) ,表示起点位于第 rr 行第 cc 列。
第三行包含两个数 x,yx,y (1 <= x,y <= 10^9)(1<=x,y<=109) ,表示最多向左或向右移动的次数。
接下来 nn 行描述这个迷宫，每行为一个长为 mm 的由 '.' 和 '*' 组成的字符串。 '.' 表示空地， '*' 表示障碍。 输入保证起点不是障碍。
输出格式：
输出一个整数，表示从起点出发可以到达的格子数，包括起点本身。
刚开始写的时候是先写的dfs（深度搜索），显然wa了
本题要求：搜索所有能到达的点的个数，还有一个附加条件：向左向右的次数是有限的！
First example: s（3，2） x=1，y=2
+表示可以访问的点，我们可以看到（1，3）这个点并不是 2+2=4
这是因为先走到了点（1，1）此时的 r 为0，一直走到r=2时，就为（1，3）
+++.. +***. +++** *+++.
所以本题不是简单的 坐标比S.y-maxr大，比S.y+maxl小就行了
于是用dfs出现了一个问题，刚才访问过的点显然并不是最短路径，一个点必然是有多条路径的，dfs的问题是他无法计算一个点的最小路径，如果不加visit数组让一个点重复计数，必然会达到死循环，dfs做本题不太方便
本题的坑爹点在于：一个点有许多条路径，于是就导致了一个点从不同路径进入，他的左边最小步数和右边最小步数是不同的--》于是用到了广度优先搜索（bfs）
/*以下是本题bfs的基本模板*/
while (!Q.empty())
{
v = Q.front();
Q.pop(); //弹出一个
for (int i = 0;i < 4;i++)
{
p = v;
p.x += a1[i];
p.y += a2[i];
if (i == 1) p.l += 1;
if (i == 2) p.r += 1;
if (check(p.x,p.y,p.l,p.r)) //这个点可不可取
{
visit[p.x][p.y] = 1;
number++;
cnt[p.x][p.y].l = p.l;
cnt[p.x][p.y].r = p.r;
Q.push(p);
}
}
}可以发现，如果bfs只按照这个模板进去，就会发现上述问题，没有选择到一个最短路径，会wa几个点，bfs虽然可以解决一部分最短路径的问题，但终究是有限的，需要增加一个新的选择语句if，
思路：如果这个点已经访问过了，但是此时的步数比原本的步数还小，就让他替换原来的值，成为新的擂主，然后同时入队（因为这个点已经最小了，那么同时他周围的点也可能会取到最小值）
else if (p.x >= 0 && p.y >= 0 && p.x < n && p.y < m && visit[p.x][p.y])
{
if (p.l < cnt[p.x][p.y].l && (p.r < cnt[p.x][p.y].r))
{//两个都是最小值
cnt[p.x][p.y].l = p.l;
cnt[p.x][p.y].r = p.r;
Q.push(p);
}
if ((p.l < cnt[p.x][p.y].l && p.r > cnt[p.x][p.y].r) || p.r < cnt[p.x]
[p.y].r && p.l > cnt[p.x][p.y].l)//其中一个小于最小值
Q.push(p);
}源代码如下
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int r, c;
int maxl, maxr;
char s[2005][2005] = { 0 };
int visit[2005][2005];
int a1[] = { -1,0,0,1 }; //上下移动
int a2[] = { 0,-1,1,0 }; //左右移动
struct node
{
int x, y;
long l;
long r;
};
struct point
{
long l;
long r;
};
point cnt[2005][2005];
queue<node> Q;
bool check(int i, int j, int l, int r)//判断这一步是否可走
{ //******注意此时由于是长方形，所以j<m,要注意不要写成j<n！！！！
return (i >= 0 && i < n&& j >= 0 && j < m&& l <= maxl && r <= maxr && !visit[i][j] && s[i][j] != '*');
//判断是否走出地图，左右移动步数是否满足要求以及是否走过这个点并且这个点可以走
}
int bfs(int x, int y)
{
int number = 0;
node p;
node v = { x,y,0,0 };
cnt[x][y].l = cnt[x][y].r = 0;
if (Q.empty())
Q.push(v);
visit[r][c] = 1;
number++;
while (!Q.empty())
{
v = Q.front();
Q.pop(); //弹出一个
for (int i = 0;i < 4;i++)
{
p = v;
p.x += a1[i];
p.y += a2[i];
if (i == 1) p.l += 1;
if (i == 2) p.r += 1;
if (check(p.x, p.y, p.l, p.r))
{
visit[p.x][p.y] = 1;
number++;
cnt[p.x][p.y].l = p.l;
cnt[p.x][p.y].r = p.r;
Q.push(p);
}
else if (p.x >= 0 && p.y >= 0 && p.x < n && p.y < m && visit[p.x][p.y])
{
if (p.l < cnt[p.x][p.y].l && (p.r < cnt[p.x][p.y].r))
{
cnt[p.x][p.y].l = p.l;
cnt[p.x][p.y].r = p.r;
Q.push(p);
}
if ((p.l < cnt[p.x][p.y].l && p.r > cnt[p.x][p.y].r)）
Q.push(p);
if(p.r < cnt[p.x][p.y].r && p.l > cnt[p.x][p.y].l)
//其中一个小于最小值
Q.push(p);
}
}
}
return number;
}
int main()
{
memset(cnt, 0x3f, sizeof(cnt));
int number = 0;
cin >> n >> m; //迷宫长度
cin >> r >> c; //起点
r--;c--;
cin >> maxl >> maxr; //向左向右最大移动次数
for (int i = 0;i < n;i++)
for (int j = 0;j < m;j++)
{
cin >> s[i][j];
}
number = bfs(r, c);
cout << number;
return 0;
}