欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-10 09:11:00
...

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

题解:bfs+优先队列
因为向左、向右都限制了步数,导致有的地方因为vis数组的原因无法访问。
xxxxxxx
...xxxx
.x.x.
.x.x.xx
.x.....
.xxxxx.
.S.....

S是起点,假设向右能走5步,那么图中标红的点就无法到达,因为向右走的那条路线将其他路线能走的点的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;
}