写的01bfs, 94分, 下载不了数据
查看原帖
写的01bfs, 94分, 下载不了数据
675527
Play_CP_4fun楼主2023/2/24 03:40
/*
Author: SJ
*/
#include<bits/stdc++.h>
const int N = 1000 + 10;
using ll = long long;
using ull = unsigned long long;

/*这个问题显然能建出无向图用最短路求解, 然后观察得知
图中边权只有0, 1两种.用0-1bfs求解将时间复杂度从O(mlogm)
降为O(|E|), 在这题也就是O(rc);
*/

/*
写代码一定要优美
*/
int t, r, c, dis[N][N];
bool vis[N][N];
char g[N][N];
std::string check = "\\/\\/";
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
int dx2[] = {-1, -1, 0, 0}, dy2[] = {-1, 0, 0, -1};
struct st {
	int x, y;
};
std::deque<st> dq;
void init() {
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);

	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			std::cin >> g[i][j];
}
void bfs() {
	dq.push_front({1, 1});
	vis[1][1] = 1;
	dis[1][1] = 0;
	while (!dq.empty()) {
		st tmp = dq.front();
		int x1 = tmp.x, y1 = tmp.y;
		dq.pop_front();
		vis[x1][y1] = 1;

		// std::cout << x1 << ' ' << y1 << "\n";
		for (int i = 0; i < 4; i++) {
			int x2 = x1 + dx[i], y2 = y1 + dy[i], x3 = x1 + dx2[i], y3 = y1 + dy2[i];
			// std::cout << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << "\n";
			if (x2 < 1 || x2 > r + 1 || y2 < 1 || y2 > c + 1) continue;
			if (vis[x2][y2]) continue;
			int w = 0 + (g[x3][y3] != check[i]);
			// std::cout << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << ' ' << g[x3][y3] << ' ' << check[i] << ' ' << w << "\n";

			if (dis[x2][y2] > dis[x1][y1] + w) {
				dis[x2][y2] = dis[x1][y1] + w;
				if (!w) dq.push_front({x2, y2});
				else dq.push_back({x2, y2});
			}
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	// std::cin >> t;
	// while (t--) {
		std::cin >> r >> c;
		init();
		if ((r + c) % 2 != 0) {
			std::cout << "NO SOLUTION" << "\n";
			// continue;
		}
		bfs();
		std::cout << dis[r + 1][c + 1] << "\n";
	// }
	return 0;
}

想求一下3号点的数据

2023/2/24 03:40
加载中...