할로윈묘지

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #define INF 987654321 using namespace std; int map[31][31], dist[31][31]; typedef struct Pos { int sx, sy, ex, ey, cost; } Pos; int dx[4] = { 0, 0, -1,1 }, dy[4] = { -1,1,0,0 }; vector<Pos> v; int main() { while (1) { int w, h, g, e; scanf("%d%d", &w, &h); if (w == 0 && h == 0) break; v.clear(); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { dist[i][j] = INF; map[i][j] = 0; } } scanf("%d", &g); int x, y; for (int i = 0; i < g; i++) { scanf("%d%d", &x, &y); map[y][x] = 1; //묘비가 있음 -> 지나갈 수 없다. } scanf("%d", &e); int x1, y1, x2, y2, t; for (int i = 0; i < e; i++) { scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &t); //귀신 구멍 v.push_back({ x1, y1, x2, y2, t }); map[y1][x1] = 2; } //input //start (0, 0) end(w-1, h-1 //좌표의 노드화 map[h - 1][w - 1] = 2; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (!map[i][j]) { //묘비가 아닐 때 for (int d = 0; d < 4; d++) { int nx = j + dx[d]; int ny = i + dy[d]; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; if (map[ny][nx] == 1) continue; v.push_back({ j, i, nx, ny, 1 }); } } } } dist[0][0] = 0; //벨만포드 for (int i = 0; i < w * h - g; i++) { //묘비의 개수를 뺀 만큼 확인한다. for (int j = 0; j < v.size(); j++) { if (dist[v[j].sy][v[j].sx] != INF && dist[v[j].ey][v[j].ex] > dist[v[j].sy][v[j].sx] + v[j].cost) { dist[v[j].ey][v[j].ex] = dist[v[j].sy][v[j].sx] + v[j].cost; } } } bool loop = 0; //check for (int j = 0; j < v.size(); j++) { if (dist[v[j].sy][v[j].sx] != INF && dist[v[j].ey][v[j].ex] > dist[v[j].sy][v[j].sx] + v[j].cost) { loop = true; break; } } if (loop) printf("Never\n"); else if (dist[h - 1][w - 1] == INF) printf("Impossible\n"); else printf("%d\n", dist[h - 1][w - 1]); } return 0; }