bfs的题
因为每次都模拟流行砸下来,tle一次,(应该标记每个点被砸的时间)
因为没有标记走过的点不能再走,tle了一次,(之前认为走过的点应该可以再走,其实仔细想的话,走过的点一定是不能再走的)
因为没有提前判断必死的情况,tle一次,
因为题上说0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300,所以人能走的点的范围一个时(0 ≤ Xi ≤ 301; 0 ≤ Yi ≤ 301),人能走的范围最少应该比彗星的范围多1,不然人必死。而我实际代码写成了
if (temp.x < 0 || temp.x > 300 || temp.y < 0 || temp.y > 300)continue;
wa了一次
最终代码
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <stack>
#include <stdlib.h>
#include <stdio.h>#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define l(x) x<<1
#define r(x) x<<1|1
#define ms(a,b) memset(a,b,sizeof(a))using namespace std;struct node {int x, y, times;node(int xx,int yy) : x(xx), y(yy), times(0) {}node() : x(0), y(0), times(0) {}
};int mmap[333][333],vis[333][333];
int m,a,b,c;
int dir[4][2] = { 0,1,0,-1,1,0,-1,0};void setm(int x, int y,int now) {mmap[x][y] = min(mmap[x][y], now);if (x > 0) mmap[x - 1][y] = min(mmap[x - 1][y], now);if (y > 0) mmap[x][y - 1] = min(mmap[x][y - 1], now);if (x < 301) mmap[x + 1][y] = min(mmap[x + 1][y], now);if (y < 301) mmap[x][y + 1] = min(mmap[x][y + 1], now);
}int bfs() {queue<node> q;node now;node temp;q.push(now);while (!q.empty()) {now = q.front();q.pop();temp = now;temp.times++;for (int j = 0; j < 4; j++) {temp.x = now.x + dir[j][0];temp.y = now.y + dir[j][1];if (temp.x < 0 || temp.x > 301 || temp.y < 0 || temp.y > 301)continue;if (vis[temp.x][temp.y] == 1)continue;vis[temp.x][temp.y] = 1;if (mmap[temp.x][temp.y] == INF)return temp.times;if (temp.times < mmap[temp.x][temp.y])q.push(temp);}}return -1;
}int main() {ms(mmap, INF);ms(vis, 0);scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%d%d%d", &a,&b,&c);setm(a, b,c);}if (mmap[0][0] == 0) {printf("-1\n");}else {printf("%d\n", bfs());}return 0;
}