codeforces-D- Labyrinth

题目链接

大意：给一个图，向右和向左走的次数是有限的，但是向上和向下可以无限走，问能经过图中哪些点。

题解：最开始写了一个简单的bfs，没过，然后学长给了一个样例（下面会写到），确实普通的bfs有些情况会漏掉。后来改为每一次push的时候，先判断上下的点，并添加到队头，然后判断左右的点，并添加到队尾。（并不知道为什么这样写）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
//#include<map>
typedef long long LL;
using namespace std;



struct node {
	int x, y, l, r;
}temp;
char mapp[2002][2002];
int used[2002][2002];
int m, n, c, r, maxl, maxr;
deque<node>P;

int judge(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m)return 1;
	else return 0;
}

int main() {
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//cin >> n >> m >> r >> c >> maxl >> maxr;
	scanf_s("%d%d%d%d%d%d", &n, &m, &r, &c, &maxl, &maxr);
	for (int i = 0; i < n; i++) cin >> mapp[i]; 
		//scanf_s("%s", &mapp[i]);
	c--; r--;
	int ans = 0;
	memset(used, 0, sizeof(used));
	used[r][c] = 1;
	temp.x = r; temp.y = c; temp.l = maxl; temp.r = maxr;
	P.push_back(temp);
	while (!P.empty()) {
		ans++;
		temp = P.front(); P.pop_front();
		//cout << temp.x << " " << temp.y <<" "<<temp.l<<" "<<temp.r<< endl;
		for (int i = 1; i <= n; i++) {
			if (mapp[temp.x + i][temp.y] == '*')break;
			if (!judge(temp.x + i, temp.y))break;
			if (used[temp.x + i][temp.y] == 1)break;//提前退出节省时间，下同
			if (judge(temp.x + i, temp.y) && mapp[temp.x + i][temp.y] == '.'&&used[temp.x + i][temp.y] == 0) {
				node ttemp; ttemp = temp; ttemp.x = temp.x + i;
				used[temp.x + i][temp.y] = 1;
				P.push_front(ttemp);//上下的点添加到队头
			}
		}
		for (int i = 1; i <= n; i++) {
			if (mapp[temp.x - i][temp.y] == '*')break;
			if (!judge(temp.x - i, temp.y))break;
			if (used[temp.x - i][temp.y] == 1)break;
			if (judge(temp.x - i, temp.y) && mapp[temp.x - i][temp.y] == '.'&&used[temp.x - i][temp.y] == 0) {
				node ttemp; ttemp = temp; ttemp.x = temp.x - i;
				used[temp.x - i][temp.y] = 1;
				P.push_front(ttemp);
			}
		}
		if (judge(temp.x, temp.y + 1) && mapp[temp.x][temp.y + 1] == '.'&&used[temp.x][temp.y + 1] == 0 && temp.r > 0) {
			node ttemp; ttemp = temp; ttemp.y = temp.y + 1; ttemp.r--;
			used[temp.x][temp.y + 1] = 1;
			P.push_back(ttemp);//左右的点添加到队尾
		}
		if (judge(temp.x, temp.y - 1) && mapp[temp.x][temp.y - 1] == '.'&&used[temp.x][temp.y - 1] == 0 && temp.l > 0) {
			node ttemp; ttemp = temp; ttemp.y = temp.y - 1; ttemp.l--;
			used[temp.x][temp.y - 1] = 1;
			P.push_back(ttemp);
		}

	}
	cout << ans;
}

普通dfs wa的样例：

20 7
3 6
5 2
......*
.****.*
.****.*
....*.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**....*
*******