[백준 3860] 할로윈 묘지 (C++)

문제 링크: https://www.acmicpc.net/problem/3860

3860번: 할로윈 묘지

1. 주의할 점

- 매 TC마다 초기화 필수

- 도착지점에서 뻗어나가는 간선은 존재하면 안된다

- 간선형태로 정보를 저장한다 (Y좌표 * 너비 + X좌표)

 

2. 구현

- 묘비의 위치에는 Arr[][]배열에서 -1을 저장한다

- Make_graph() 함수를 통해 일반적인 이동의 경우 그래프에 추가한다

- Bellman_ford() 함수를 통해 Dist[]를 계속 Row*Col번 갱신하며, Row*Col번 일때 Dist[]가 갱신된다면 음의 값을 가지는 순환 사이클이 있다고 판단하여 Never를 출력하도록 한다 

 

#define MAX 987654321
#include <iostream>
#include <vector>
using namespace std;
struct info {
	int to,val;
};
info tmp;
int row, col, tomb, tx, ty, hole, ex, ey, ax, ay, t;
int arr[31][31];
bool ghost[31][31];
bool cycle;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
vector<info> v[901];		//row*col+col
int dist[901];

void make_graph() {
	//한 노드에서 다른 노드로 갈 수 있는 경우 v[]에 추가
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (arr[i][j] == -1 || (i*col+j==row*col-1) || ghost[i][j]) continue;
			for (int k = 0; k < 4; k++) {
				int nx = j + dx[k];
				int ny = i + dy[k];
				if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx] != -1) {
					int a = i * col + j;
					int b = ny * col + nx;
					tmp.to = b;
					tmp.val = 1;
					v[a].push_back(tmp);
				}
			}
		}
	}
}

void bellman_ford() {
	//Node의 수+1 만큼 수행
	for (int i = 0; i <= row * col; i++) {
		for (int j = 0; j < row * col; j++) {
			if (dist[j] == MAX) continue;
			for (int k = 0; k < v[j].size(); k++) {
				int to = v[j][k].to;
				int val = v[j][k].val;
				int d = dist[j] + val;
				if (d != MAX && dist[to] > d) {
					if (i == (row * col)) 	cycle = true;					
					dist[to] = d;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	while (1) {
		cin >> col >> row;
		if (row == 0 && col == 0) break;			
		//초기화
		for (int i = 0; i < row; i++)
			for (int j = 0; j < col; j++) {
				ghost[i][j] = false;
				arr[i][j] = 0;
			}
		cycle = false;
		for (int i = 0; i <= row * col; i++) {
			dist[i] = MAX;
			v[i].clear();
		}
		dist[0] = 0;

		cin >> tomb;
		for (int i = 0; i < tomb; i++) {
			cin >> tx >> ty;
			arr[ty][tx] = -1;
		}
		cin >> hole;
		for (int i = 0; i < hole; i++) {
			cin >> ex >> ey >> ax >> ay >> t;
			int a = ey * col + ex;
			int b = ay * col + ax;
			tmp.to = b;
			tmp.val = t;
			v[a].push_back(tmp);
			ghost[ey][ex] = true;
		}
		make_graph();
		bellman_ford();
		if (cycle) cout << "Never\n";
		else if (dist[row*col-1] == MAX) cout << "Impossible\n";
		else cout << dist[row*col - 1] << '\n';
	}
	system("pause");
	return 0;
}