[16137번] 견우와 직녀

16137번: 견우와 직녀

 

www.acmicpc.net

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct pnt { int rr, cc; }temp;
queue<pnt>Cliff, Q, temp_Q;
int N, M;
int Map[10][10];
int visit[10][10];
int temp_arr[10][10];//visit 바뀌기 전 정보를 저장
int drc[] = { 0,0,-1,1,-1,1,0,0 };
int min_temp = 10000;

bool chk(int r, int c) {
	char flag = true;
	if (r - 1 >= 0 && c + 1 < N) {
		if (Map[r - 1][c] == 0 && Map[r][c + 1] == 0) flag = false;
	}
	if (r - 1 >= 0 && c - 1 >= 0) {
		if (Map[r - 1][c] == 0 && Map[r][c - 1] == 0) flag = false;
	}
	if (r + 1 < N && c + 1 < N) {
		if (Map[r][c + 1] == 0 && Map[r + 1][c] == 0) flag = false;
	}
	if (r + 1 < N&&c - 1 >= 0) {
		if (Map[r][c - 1] == 0 && Map[r + 1][c] == 0) flag = false;
	}
	return flag;
}


void Go() {
	while (!Q.empty()) {
		int r = Q.front().rr;
		int c = Q.front().cc;
		Q.pop();
		for (int d = 0; d < 4; d++) {
			int nr = r + drc[d];
			int nc = c + drc[d + 4];
			if (!(nr < 0 || nr >= N || nc < 0 || nc >= N)) {
				if (visit[nr][nc] > visit[r][c] + 1) {
					if (Map[nr][nc] == 1) {
						visit[nr][nc] = visit[r][c] + 1;
						temp.rr = nr;
						temp.cc = nc;
						Q.push(temp);
					}
					else if (Map[nr][nc] > 1) {
						if (Map[r][c] == 1) {
							visit[nr][nc] = Map[nr][nc] * (visit[r][c] / Map[nr][nc] + 1);
							temp.rr = nr;
							temp.cc = nc;
							Q.push(temp);
						}
					}
				}
			}
		}
	}
	if (min_temp > visit[N - 1][N - 1]) {
		min_temp = visit[N - 1][N - 1];
	}
}

void copy_arr(int(*arr1)[10], int(*arr2)[10]) { //arr1 <- arr2
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			arr1[i][j] = arr2[i][j];
		}
	}
}

void put_Bridge() {
	while (!Cliff.empty()) {
		int r = Cliff.front().rr;
		int c = Cliff.front().cc;
		Cliff.pop();
		if (chk(r, c) == true) {
			Map[r][c] = M;
			copy_arr(temp_arr, visit);//탐색 전 visit정보를 저장
			temp_Q = Q;
			Go();
			Q = temp_Q;
			copy_arr(visit, temp_arr);//visit 다시 복구
			Map[r][c] = 0;
		}
	}
}

int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			visit[i][j] = 1000;
		}
	}
	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> Map[r][c];
			if (Map[r][c] == 0) {
				temp.rr = r;
				temp.cc = c;
				Cliff.push(temp);
			}
		}
	}
	temp.rr = 0;
	temp.cc = 0;
	Q.push(temp);
	visit[0][0] = 0;
	if (Cliff.size() == 0) Go();
	else put_Bridge();
	cout << min_temp;
}