社区讨论

RE 21分求救!(DEV是对的) 大佬帮着看看

P2895[USACO08FEB] Meteor Shower S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lxybhfd7
此快照首次捕获于
2024/06/28 14:33
2 年前
此快照最后确认于
2024/06/28 17:54
2 年前
查看原帖
代码
CPP
#include<bits/stdc++.h>
#define MAXN 310
using namespace std;
struct coord {
	int x,y;
};
queue<coord> Q;
int ans[MAXN][MAXN],death[MAXN][MAXN];
int wk[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
int m,Ans = 100000;
int main() {
	memset(ans,-1,sizeof(ans));
	memset(death,0x7f,sizeof(death));
	cin >> m;
	for(int i = 1;i <= m;i++) {
		int x,y,t;
		cin >> x >> y >> t;
#define MIN(x,y,t) if(x >= 0 && y >= 0) death[x][y] = min(death[x][y],t)
		MIN(x,y,t);
		for(int k = 0; k < 4; k++) MIN(x + wk[k][0],y + wk[k][1],t);
	}
	Q.push((coord){0,0});
	ans[0][0] = 0;
	while(!Q.empty()) {
		coord u = Q.front();
		int ux = u.x,uy = u.y;
		Q.pop();
		for(int k = 0;k < 4;k++) {
			int x = ux + wk[k][0],y = uy + wk[k][1];
			if(x < 0 || y < 0 || ans[x][y] != -1 || ans[ux][uy] + 1 >= death[x][y]) continue;
			ans[x][y] = ans[ux][uy] + 1;
			Q.push((coord){x,y});
		}
	}
	for(int i = 0;i <= 305;i++) {
		for(int j = 0;j <= 305;j++) {
			if(death[i][j] > 1000 && ans[i][j] != -1) Ans = min(Ans,ans[i][j]);
		}
	}
	if(Ans == 100000) puts("-1");
	else cout << Ans;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...