#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int MAX = 50005; //隕石最大數量 class data { public: int x, y, Time; }; data s[MAX]; //隕石墜落的位置和時間 int map[305][305], M; //map表示point（i， j）位置運算墜落的最早時間。 bool safe[305][305], vis[305][305]; //safe是安全的地方，則為true int xy[4][2] = {⑴, 0, 0, 1, 1, 0, 0, ⑴};//4個方位 int bfs() { queue<data>que; data temp, te; temp.x = temp.y = temp.Time = 0; //開始位置0，0和時間為0； que.push(temp); vis[0][0] = true; //標記已返問過 while(!que.empty()) { te = que.front(); que.pop(); for(int i = 0; i < 4; i++) //4個方位進行搜索 { int x = te.x + xy[i][0]; int y = te.y + xy[i][1]; int time = te.Time + 1; if(x >= 0 && y >= 0 && map[x][y] > time && !vis[x][y]) //沒返問過的，隕石還衰敗下的位置可以走 { if(safe[x][y]) //如果找到安全地方，返回時間。 return time; vis[x][y] = true; //標記已返問過 temp.x = x; temp.y = y; temp.Time = time; que.push(temp); //入隊 } } } return ⑴; //不能找到安全地方 } int main() { // freopen("data.txt", "r", stdin); //這里忘記注釋掉了，wr了1次，坑 int i, j, k; while(scanf("%d", &M) != EOF) { memset(safe, true, sizeof(safe)); //初始化safe memset(vis, false, sizeof(vis)); //初始化vis for(i = 0; i < 305; i++) //初始化map for(j = 0; j < 305; j++) map[i][j] = 10000000; for(i = 0; i < M; i++) { scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].Time); safe[s[i].x][s[i].y] = safe[s[i].x - 1][s[i].y] = safe[s[i].x][s[i].y - 1] = safe[s[i].x + 1][s[i].y] = safe[s[i].x][s[i].y + 1] = false; //標記隕石會砸到的地方 } data temp; for(j = 0; j < M; j++) //更新map中每個位置隕石最早掉落的時間，注意，是最早的時間。 { //剛開始忘記斟酌這1點了。墜落的時間不是降序 temp = s[j]; if(map[temp.x][temp.y] > temp.Time) map[temp.x][temp.y] = temp.Time; for(k = 0; k < 4; k++) { int x = temp.x + xy[k][0]; int y = temp.y + xy[k][1]; if(x >= 0 && y >= 0 && map[x][y] > temp.Time) map[x][y] = temp.Time; } } if(map[0][0] == 0) //開始時，隕石就砸下來了，就直接死掉了，⑴； printf("⑴ "); else printf("%d ", bfs()); } return 0; }