北大ACM3669――Meteor Shower~~简单的广搜

#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; }