专栏文章

SnackOI R1-C 山峰之上 题解

lliangjindong0504
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpl65s
此快照首次捕获于
2025/12/02 06:16
3 个月前
此快照最后确认于
2025/12/02 06:16
3 个月前
查看原文

闲话

这题太吃操作了。

nn 较小的部分分

非常直观啊，可以直接设 disi,j,k,0/1/2dis_{i,j,k,0/1/2} 表示当前在 i,j{i,j}，第 kk 个月，在水里泡了 0/1/20/1/2 月，最少的步数。
我们考虑 dijkstra，每次遍历到一个 i,j,k,0/1/2i,j,k,0/1/2 就进行转移。转移分为两种，移动和不移动。细节稍微有点多。需要注意的是，如果当前第四个数是 22，那么不能走到河里。期望得分 44pts44pts，实际上可以获得更高的分数。

特殊性质

特殊性质 BCD，直接输出 2n−12n - 1，期望得分 48pts48pts。
特殊性质 BD，直接跑 bfs，期望得分 52pts52pts。
特殊性质 B，发现月份这一维就没啥用了，直接把这一维弄掉，跑 dij，期望得分 64pts64pts。
特殊性质 D，可以直接 bfs，因为边权全都是 1 了。期望得分 76pts76pts。
特殊性质 A 和 C 可以让你减少一点点码量，但是基本没啥用（（（

正解

01bfs。处理边权为 0 或 1 的图。
具体地，开一个 deque，如果边权是 0，就把这个元素插入前面，否则插入后面。这样也可以保持 dis 递增的原则。期望得分 100pts100pts。
献上代码。
CPP
#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int N = 1010;
const int M = 13;
const int K = 3;

const int INF = 1e9;

int d[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

struct V {
	int x, y;	
};

struct node {
	int x, y, month, water;	
};

int ans;

int n, m, z;
int l[N][N], r[N][N];

int dis[N][N][M][K];

bool vis[N][N][M][K];

char a[N][N];

std::deque <node> q;
std::pair <int, int> river[N * N];

bool check (int x, int y, int mon) {
	if (l[x][y] <= r[x][y]) {
		return (mon >= l[x][y] && mon <= r[x][y]);
	}
	return (mon >= l[x][y] || mon <= r[x][y]);
}

int next_month (int x) {
	if (x == 12) {
		return 1;
	}
	return x + 1;
}

int main() {
	#ifndef ONLINE_JUDGE
        freopen("peak25.in", "r", stdin);
        freopen("peak25.out", "w", stdout);
    #endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr); 

	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			std::cin >> a[i][j];
			
			if (a[i][j] == 'R') {
				river[z++] = {i, j};
			}
		}
	}
	for (int i = 1; i <= z; ++i) {
		std::cin >> l[river[i - 1].first][river[i - 1].second] >> r[river[i - 1].first][river[i - 1].second];
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			for (int k = 1; k <= 12; ++k) {
				for (int l = 0; l <= 2; ++l) {
					dis[i][j][k][l] = INF;
				}
			}
		}
	}
	dis[1][1][1][0] = 1;
	q.push_back((node){1, 1, 1, 0});
	
	while (!q.empty()) {
		node now = q.front();
		q.pop_front();
		
		int nx = now.x, ny = now.y, nm = now.month, nw = now.water;
		
		if (vis[nx][ny][nm][nw]) {
			continue;
		}
		vis[nx][ny][nm][nw] = 1;
		//std::cout << "F:" << nx << ' ' << ny << ' ' << nm << ' ' << nw << std::endl;
		
		//stay
		int tm = next_month(nm);
		if (a[nx][ny] == 'R' && !check(nx, ny, next_month(nm))) {
			if (nw < 2 && dis[nx][ny][nm][nw] + 1 < dis[nx][ny][tm][nw + 1]) {
				dis[nx][ny][tm][nw + 1] = dis[nx][ny][nm][nw] + 1;
				q.push_back((node){nx, ny, tm, nw + 1});
			}
		} else {
			if (dis[nx][ny][nm][nw] + 1 < dis[nx][ny][tm][0]) {
				dis[nx][ny][tm][0] = dis[nx][ny][nm][nw] + 1;
				q.push_back((node){nx, ny, tm, 0});
			}
		}

		//move
		for (int f = 0; f < 4; ++f) {
			int tx = nx + d[f][0], ty = ny + d[f][1];
			if (tx && ty && tx <= n && ty <= m && a[tx][ty] != '#') {
				int add = 0, tm = nm;
				if (a[nx][ny] != 'N') {
					add = 1, tm = next_month(nm);
				}

				if (a[tx][ty] == 'R' && !check(tx, ty, tm)) {
					if (nw >= 2) {
						continue;
					}
					if (dis[nx][ny][nm][nw] + add < dis[tx][ty][tm][nw + 1]) {
						dis[tx][ty][tm][nw + 1] = dis[nx][ny][nm][nw] + add;
						if (add) {
							q.push_back((node){tx, ty, tm, nw + 1});
						} else {
							q.push_front((node){tx, ty, tm, nw + 1});
						}
					}
				} else {
					if (dis[nx][ny][nm][nw] + add < dis[tx][ty][tm][0]) {
						dis[tx][ty][tm][0] = dis[nx][ny][nm][nw] + add;
						if (add) {
							q.push_back((node){tx, ty, tm, 0});
						} else {
							q.push_front((node){tx, ty, tm, 0});
						}
					}
				}
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
	 	for (int j = 1; j <= n; ++j) {
	 		ans = INF;
	 		for (int k = 1; k <= 12; ++k) {
	 			for (int l = 0; l <= 2; ++l) {
	 				ans = std::min(ans, dis[i][j][k][l]);
	 			}
	 		}
	 		if (ans == INF) {
	 			//std::cout << "0 ";
	 			continue;
			}
	 		//std::cout << ans << ' ';
	 	}
	 	//std::cout << std::endl;
	}

	ans = INF;
	for (int k = 1; k <= 12; ++k) {
		for (int l = 0; l <= 2; ++l) {
			ans = std::min(ans, dis[n][m][k][l]);
		}
	}
	if (ans == INF) {
		std::cout << -1;
	} else {
		std::cout << ans;
	}

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...