本文共 1265 字，大约阅读时间需要 4 分钟。
需要自己转化为迷宫问题！
#include #include #include #include using namespace std;#define MAX1 50005#define MAX2 350int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };int M, N;typedef pair P;int maze[MAX2][MAX2];int d[MAX2][MAX2];int x[MAX1], y[MAX1], t[MAX1];int bfs(){ if (maze[0][0] == 0)return -1;//开局就炸 queue que; que.push(P(0, 0)); d[0][0] = 0; int x, y; while (!que.empty()) { P p = que.front(); que.pop(); x = p.first; y = p.second; if (maze[x][y] == INT_MAX)return d[x][y]; //安全。 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && ny >= 0 && d[nx][ny] == INT_MAX&&d[x][y] + 1 < maze[nx][ny])//是否可以移动，是否访问过，是否安全。 { que.push(P(nx, ny)); d[nx][ny] = d[x][y] + 1; } } } return -1;}int main(){ int n; cin >> n; for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> t[i]; fill(maze[0], maze[0] + MAX2*MAX2, INT_MAX); //构建迷宫，安全位置里放INT_MAX fill(d[0], d[0] + MAX2*MAX2, INT_MAX); //d中放人在该位置的时间，无穷代表没被访问， for (int i = 0; i < n; i++) { maze[x[i]][y[i]] = min(maze[x[i]][y[i]], t[i]); //迷宫里放炸的时间，INX_MAX代表安全 for (int j = 0; j < 4; j++) { int nx = x[i] + dx[j]; int ny = y[i] + dy[j]; if (nx >= 0 && ny >= 0) maze[nx][ny] = min(maze[nx][ny], t[i]); } } cout << bfs(); system("pause");}
转载地址：http://qzyci.baihongyu.com/