CodeForces 1064D Labyrinth (bfs+优先队列)

题意：给出一个图，有障碍，给出起点坐标，以及向左、向右限制的步数，求最多能走多少个点。

题解：bfs+优先队列
因为向左、向右都限制了步数，导致有的地方因为vis数组的原因无法访问。
ｘｘｘｘｘｘｘ
．．．ｘｘｘｘ
．ｘ．ｘ．．．
．ｘ．ｘ．ｘx
．ｘ．．．．．
．ｘｘｘｘｘ．
．Ｓ．．．．．

Ｓ是起点，假设向右能走５步，那么图中标红的点就无法到达，因为向右走的那条路线将其他路线能走的点的vis置1了。

这样一来，我们可以考虑对于剩余步数多的点先走，就不会出现上述情况。
我们可以用优先队列来做，注意结构体中的运算符比较。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
int n, m, r, c, x, y, dir[5][5] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }, ans;
char g[2222][2222];
bool vis[2222][2222];
struct node {
	int r, c, x, y, t;
	node() {}
	node(int r, int c, int x, int y,int t) :r(r), c(c), x(x), y(y), t(t) {}
	bool operator < (const node m)const {
		return t > m.t;
	}
};
bool check(int x, int y) {
	if (x <= 0 || x > n || y <= 0 || y > m || vis[x][y] || g[x][y] == '*') return false;
	return true;
}
priority_queue<node> q;
void bfs() {
	node no = node{ r, c, x, y, 0 };
	q.push(no);
	vis[r][c] = 1;
	while (!q.empty()) {
		node temp = q.top();
		q.pop();
		ans++;
		for (int i = 0; i < 4; i++) {
			if (check(temp.r + dir[i][0], temp.c + dir[i][1])) {
				if (i == 3 && temp.x + dir[i][1] < 0) continue;
				if (i == 2 && temp.y - dir[i][1] < 0) continue;
				int xx = temp.x, yy = temp.y, tt = temp.t;
				if (i == 3) xx += dir[i][1], tt++;
				if (i == 2) yy -= dir[i][1], tt++;
				q.push(node{ temp.r + dir[i][0], temp.c + dir[i][1], xx, yy, tt });
				vis[temp.r + dir[i][0]][temp.c + dir[i][1]] = true;
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &r, &c, &x, &y);
	for (int i = 1; i <= n; i++) {
		scanf("%s", g[i] + 1);
	}
	bfs();
	printf("%d\n", ans);
	return 0;
}