违规用户名690561 @ 2022-07-23 10:33:48
最后3个点WA了……
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
struct node {
long long x1, y1, z1;
} t1, s;
queue<node> q;
long long m, t[1005], x[1005], y[1005], a[400][400], b[400][400];
int dx[] = {-1, 1, 0, 0, 0};
int dy[] = {0, 0, -1, 1, 0};
void BFS(int xx, int yy, int zz) {
t1 = {xx, yy, zz};
q.push(t1);
while(!q.empty()) {
t1 = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int xxx = t1.x1 + dx[i];
int yyy = t1.y1 + dy[i];
if(xxx >= 0 && yyy >= 0 && b[xxx][yyy] == 0) {
b[xxx][yyy] = 1;
if(c[xxx][yyy] == 0) {
printf("%d", t1.z1 + 1);
exit(0);
} else {
s = {xxx, yyy, t1.z1 + 1};
if(s.z1 < a[xxx][yyy] - 1) {
q.push(s);
}
}
}
}
}
}
int main() {
scanf("%d", &m);
b[0][0] = 1;
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &x[i], &y[i], &t[i]);
if(a[x[i]][y[i]] == 0) {
a[x[i]][y[i]] = t[i] + 1;
}else{
if(a[x[i]][y[i]] > t[i] + 1){
a[x[i]][y[i]] = t[i] + 1;
}
}
if(a[x[i]][y[i]] != 0){
c[x[i]][y[i]] = 1;
}
if(x[i] - 1 >= 0) {
if(a[x[i] - 1][y[i]] == 0){
a[x[i] - 1][y[i]] = t[i] + 1;
}else{
if(a[x[i] - 1][y[i]] > t[i] + 1){
a[x[i] - 1][y[i]] = t[i] + 1;
}
}
}
if(a[x[i] - 1][y[i]] != 0){
c[x[i] - 1][y[i]] = 1;
}
if(y[i] - 1 >= 0) {
if(a[x[i]][y[i] - 1] == 0){
a[x[i]][y[i] - 1] = t[i] + 1;
}else{
if(a[x[i]][y[i] - 1] > t[i] + 1){
a[x[i]][y[i] - 1] = t[i] + 1;
}
}
}
if(a[x[i]][y[i] - 1] != 0){
c[x[i]][y[i] - 1] = 1;
}
if(a[x[i] + 1][y[i]] == 0) {
a[x[i] + 1][y[i]] = t[i] + 1;
}else{
if(a[x[i] + 1][y[i]] > t[i] + 1){
a[x[i] + 1][y[i]] = t[i] + 1;
}
}
if(a[x[i] + 1][y[i]] != 0){
c[x[i] + 1][y[i]] = 1;
}
if(a[x[i]][y[i] + 1] == 0) {
a[x[i]][y[i] + 1] = t[i] + 1;
}else{
if(a[x[i]][y[i] + 1] > t[i] + 1){
a[x[i]][y[i] + 1] = t[i] + 1;
}
}
if(a[x[i]][y[i] + 1] != 0){
c[x[i]][y[i] + 1] = 1;
}
}
BFS(0, 0, 0);
printf("-1");
return 0;
}
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀⠛⠿⠿⣿⠃⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
by Cutata @ 2022-07-29 14:52:53
建议先改改码风!
by 违规用户名690561 @ 2022-07-29 16:46:26
@JokerYI
什么意思?能详细讲讲吗?
by Cutata @ 2022-07-30 14:03:08
@tzxxzt 主函数给地图赋初值可以循环跑一遍方位数组,减少码量,否则容易出错。
for(int i = 1; i <= m; i++){
cin >> fx >> fy >> ft;
for(int j = 0; j < 5; j++){
int nx = fx + dx[j];
int ny = fy + dy[j];
if(nx >= 0 and ny >= 0){
if(vis[nx][ny] >= 0)
vis[nx][ny] = min(vis[nx][ny], ft);
else
vis[nx][ny] = ft;
}
}
}
和你的风格可能不太一样,希望对你有帮助。
by 违规用户名690561 @ 2022-08-03 13:32:54
@JokerYI 谢谢