[ 백준 23289 ] 온풍기 안녕 ! (C++)
백준의 온풍기 안녕!(23289) 문제이다.
[ 문제풀이 ]
문제가 구현해야 할 부분도 난이도도 꽤나 있는 편인 문제이다. 문제에서 제시한 순서에 맞게 온풍기의 성능을 테스트 하였을 때, 몇 번만에 주어진 조건에 맞게 방이 설정되는지 구해야 하는 문제이다.
주어진 입력값을 관리하는 것 부터, 주어진 순서에 맞게 과정이 진행되는 사항을 과정별로 차근차근 알아보도록 하자.
(이 글을 읽기 전에, 문제를 해결하시지 못한 것은 상관이 없는데 문제에 대한 이해와 구현해야 하는 내용이 무엇인지는 완벽하게 알고 읽으시는 것을 권장드립니다.)
#1. 입력값
우리는 크게 본다면, 입력값으로 총 2가지의 정보를 입력받게 된다.
1. 맵의 구성 : 어느 좌표가 온풍기가 존재하는지, 온도를 조사해야 하는 좌표 값들을 맵에 숫자들로 입력받게 된다.
2. 벽의 상태 : 벽이 어느 위치에 어느 방향으로 벽이 세워져 있는지 입력받게 된다.
먼저, 맵의 구성을 보게 된다면 0 ~ 5까지의 숫자가 주어질 수가 있다. 0은 빈칸, 1 ~ 4는 온풍기, 5는 조사해야 할 좌표를 의미한다. 본인은 입력받음과 동시에 맵의 모든 값들을 0으로 바꿔버렸다. 왜냐하면, 본인은 맵의 좌표값에 들어가는 값을 온도로 채워나갈 것이기 때문이다.
초기에는 당연히 모든 좌표가 0도일 것이다. 그런데, 온풍기나 조사해야 할 좌표를 의미하는 1 ~ 5의 값이 처음부터 들어있다면, 온도를 계산하는데 있어서 불편함이 있을 수 있기 때문이다.
대신, 위의 정보들을 따로 어딘가에는 저장을 해주어야 한다. 그래서 본인은 vector를 선언해서 위의 값들을 관리해 주었다.
조사해야 할 좌표 값들의 정보를 저장하기 위해서 pair<int, int>를 자료형으로 갖는 Vector 하나,
온풍기에 대한 정보를 저장하기 위해서 pair<pair<int, int>, int>> 를 자료형으로 갖는 Vector 하나.
온풍기에 대한 정보는 (x , y)라는 좌표에 대한 정보도 있어야 하지만, 온풍기의 바람 방향까지도 저장을 해야 하기 때문에 위와 같이 3개의 int를 관리할 수 있도록 만들어 주었다.
두 번째로 벽에 대한 정보를 입력받게 되는데 본인은 이를 벽을 위한 맵을 하나 더 만들어서 관리해 주었다.
맵은 3차원으로 이루어져있고 bool형의 그 크기는 [MAX][MAX][4] 로 만들어 주었다.
즉, bool wallMap[MAX][MAX][4] 라는 벽에 대한 정보를 담을 수 있는 맵을 하나 만들어 주었다.
그리고 우리는 입력으로 특정 좌표 (x , y)에서 어느 방향에 벽이 있는지를 입력으로 받게 된다.
만약, (x , y)에 0의 방향으로 벽이 있다면, (x , y)와 그 위의 좌표인(x - 1 , y)사이에 벽이 있음을 의미하고, 1의 방향으로 벽이 있다면 (x , y)와 (x , y + 1) 사이에 벽이 있음을 의미한다.
즉, 정리해본다면 (x , y)에 0의 벽이 있다면, (x , y)에서 북쪽 방향으로는 벽이 있음을 의미하고, (x - 1 , y)에서는 남쪽 방향으로 벽이 있음을 의미한다. 1이라면 (x , y)에서 동쪽 방향으로 벽이 있음을, (x , y + 1)에서는 서쪽 방향으로 벽이 있음을 의미한다. 그래서 이를 wallMap에 표시를 해 주었다.
wallMap[x][y][0] = true 라는 것은, (x , y)에서 동쪽 방향으로는 벽이 있습니다.
wallMap[x][y][1] = true 라는 것은, (x , y)에서 서쪽 방향으로는 벽이 있습니다.
이런식으로 표현을 해 주었다. 본인은 방향을 { 0 , 1 , 2 , 3 } 을 { 동 , 서 , 남 , 북 } 으로 계산했기에 위와 같이 표현을 해 주었다. 이 방향은 당연히 각자 가장 편한 방식으로 지정을 해주면 된다.
지금까지 했던 이야기를 코드로 나타내면 다음과 같다.
int r, c, k, w;
int map[MAX][MAX];
bool wallMap[MAX][MAX][4];
vector<pair<int, int>> searchPos;
vector<pair<pair<int, int>, int>> heater;
vector<pair<pair<int, int>, int>> wall;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
void input() {
cin >> r >> c >> k;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> map[i][j];
if (map[i][j] != 0 && map[i][j] != 5) {
heater.push_back(make_pair(make_pair(i, j), map[i][j]));
}
else if (map[i][j] == 5) {
searchPos.push_back(make_pair(i, j));
}
map[i][j] = 0;
}
}
cin >> w;
for (int i = 0; i < w; i++) {
int a, b, c; cin >> a >> b >> c;
wall.push_back(make_pair(make_pair(a, b), c));
}
}
void settingWall() {
for (int i = 0; i < w; i++) {
int x = wall[i].first.first;
int y = wall[i].first.second;
int t = wall[i].second;
if (t == 0) {
wallMap[x][y][3] = true;
wallMap[x - 1][y][2] = true;
}
else {
wallMap[x][y][0] = true;
wallMap[x][y + 1][1] = true;
}
}
}위의 코드는, 이번문제에서 사용할 변수들과 입력값들을 관리하는 내용들을 구현한 소스코드이다.
#2. 1번과정 - 온풍기에서 바람이 나오는 과정
이제 입력도 받았고, 입력값에 따른 기본적인 세팅과정도 끝났으니 실제로 구현해야 되는 부분으로 넘어가보자.
가장 먼저, 1번 과정인 집에 있는 모든 온풍기에서 바람이 나오는 과정을 진행해보자.
바람이 나오는 과정이 참으로 마음에 들지는 않는다... 천천히 같이 진행해보자.
일단 바람이 나오게 되면 칸이 점점 멀어질 수록 숫자가 감소하는 그런 형태이면서 동시에 점점 퍼져나가는 그런 형태이다. (무슨 말인지는 저도 모르겠지만.. 문제를 보고 오셨다면 이해하실 수 있을 겁니다!)
먼저, 본인은 바람이 퍼지는 방향을 위해서 새로운 방향을 나타내는 배열을 만들어 주었다.
아래의 그림을 보면서 이야기를 계속 해보자.
온풍기가 위의 그림에서 '온풍'이라고 적혀있는 곳에 위치하고 온풍기가 오른쪽 방향으로 바람이 나올 때의 상황이다.
가장 처음에 빨강색 좌표의 온도가 5도만큼 올라가게 될 것이다.
그리고 그 이후부터는 점점 퍼져나가게 된다. 가장 첫 칸인 빨강색 칸만 퍼져나가지 않는다.
그래서 본인은 퍼져나가는 3가지 방향에 대해서 계산을 할 수 있도록 새로운 배열을 만들어 주었다.
빨강색 좌표가 (x , y)라면, 그 이후에 퍼져나가게 되는 좌표는 (x - 1 , y + 1), (x , y + 1), (x + 1 , y + 1)이 된다.
즉, x좌표는 { -1 , 0 , 1 }으로 퍼져나가게 되고, y좌표는 { 1 , 1 , 1 } 로 퍼져나가게 된다.
이 방향들을 계산할 수 있도록, 모든 방향에 대해서 만들어 준 것이다. 먼저 ,이 배열들만 보자면 다음과 같다.
int wdx[4][3] = { { -1, 0, 1 }, {-1, 0, 1 }, {1, 1, 1}, {-1, -1, -1} };
int wdy[4][3] = { { 1, 1, 1}, { -1, -1, -1 }, {-1, 0, 1 },{-1, 0, 1} };wdx,y[0][] = 온풍기의 바람이 동쪽으로 나올 때
wdx,y[1][] = 온풍기의 바람이 서쪽으로 나올 때
wdx,y[2][] = 온풍기의 바람이 남쪽으로 나올 때
wdx,y[3][] = 온풍기의 바람이 북쪽으로 나올 때 의 값을 저장해 놓은 것이다.
다시 한번 말하지만, 본인은 동서남북을 순서대로 0,1,2,3 이라는 방향으로 지정해놓고 사용했기 때문에 위와 같이 구현한 것이다. 절대로 위의 값 까지 똑같을 필요는 없다.
그러면, 빨강색 좌표에서 위의 배열을 통해서 3칸을 계산하게 되면 파랑색 칸이 계산이 되어질 것이다.
그럼, 파랑색칸에서 초록색 칸으로 가는것도 계산을 해보자. 그럼 아마 다음과 같이 계산이 될 것이다.
위와 같이 계산이 될 것이다.
가장 위의 파랑색 좌표에서는 노랑색 화살표처럼 그 다음 3칸을 계산하게 될 것이고, 가운데 파랑색 좌표에서는 회색 화살표처럼 그 다음 3칸을, 가장 아래에 있는 파랑색 좌표에서는 흰색 화살표처럼 그 다음 3칸을 계산하게 될 것이다.
그런데 ! 이러면 문제가 생긴다! 딱봐도 알겠지만, 화살표를 중복되게 받고 있는 초록색 좌표들이 존재한다. 이렇게 되면 이러한 초록색 좌표들은 값의 갱신이 여러번 일어나게 되고 제대로 온도 계산이 되지 않을 것이다.
그래서 ! "이미 한번 온도 갱신이 일어난 좌표는 더 이상 갱신시키지 않겠습니다" 라는 의미를 가지고 있는 2차원 배열을 만들어 주었다. 이 2차원 배열은 밑에서 조금 더 구체적으로 이야기해보자.
지금까지 한 이야기를 정리해보면 다음과 같다.
1. 온풍기의 바람은 첫 칸을 제외하고, 그 이후의 칸들에 대해서는 점점 퍼져나가는 특징이 있다.
2. 그래서, 점점 퍼져나가는 좌표들을 계산하기 위해서 wdx[][], wdy[][] 라는 방향을 나타내는 배열을 생성했다.
3. 2번 처럼 계산할 경우, 중복되는 좌표들이 있기 때문에, 이를 처리해줄 무언가가 필요하다.
여기까지는 좋은데, 그래서 온풍기의 바람이 나가는 저걸 어떻게 구현해야할까 ??
본인은 Queue를 이용해서 구현해주었다. 너비우선탐색(BFS)과 매우 비슷한 형태로 구현을 해 주었다.
Queue에 좌표 값과 바람의 세기를 넣어주고, 이 Queue에 들어 있는 값들을 하나씩 빼오면서 바람이 나아갈 수 있는 그 다음 좌표가 존재한다면, 그 다음 좌표를 Queue에 순차적으로 계속 넣어주면서 반복해 주었다.
물론, 그 과정에서 위에서 이야기한 "중복적으로 탐색이 되는 좌표들"을 걸러주기 위해서 bool형의 2차원 배열을 하나 만들어 주었다. bool Update[MAX][MAX] 라는 2차원 배열인데, Update[x][y] = true의 의미는 "(x , y)는 이미 온도가 한번 업데이트 된 적 있는 좌표이니 더 이상 업데이트 하지 마세요" 라는 것을 의미한다.
이 부분을 코드로 확인해보면 다음과 같다.
void spread(int x, int y, int d) {
bool update[MAX][MAX] = { false, };
d = changeMydir(d);
x += dx[d];
y += dy[d];
if (x < 1 || y < 1 || x > r || y > c) return;
queue<pair<pair<int, int>, int >> q;
q.push(make_pair(make_pair(x, y), 5));
while (q.empty() == 0) {
int x = q.front().first.first;
int y = q.front().first.second;
int wind = q.front().second;
q.pop();
map[x][y] += wind;
if (wind == 1) continue;
for (int i = 0; i < 3; i++) {
int nx = x + wdx[d][i];
int ny = y + wdy[d][i];
if (nx >= 1 && ny >= 1 && nx <= r && ny <= c) {
if (update[nx][ny] == false && checkWall(x, y, nx, ny, d, i) == true) {
update[nx][ny] = true;
q.push(make_pair(make_pair(nx, ny), wind - 1));
}
}
}
}
}
void spreadWind() {
for (int i = 0; i < heater.size(); i++) {
int x = heater[i].first.first;
int y = heater[i].first.second;
int d = heater[i].second;
spread(x, y, d);
}
}위의 코드에서 line3) 에보면, dir = changeMyDir(d) 이라는 부분이 있는데, 전혀 신경쓰지 않아도 되는 부분이다.
저 부분은, 본인이 구현을 할 때 본인이 편하게 구현할 수 있도록 문제에서 주어진 방향 말고 본인이 구현한 방향대로 방향을 바꿔서 계산하기 쉽게 만들기 위해서 넣어놓은 부분이므로 신경쓰지 않아도 된다.
위의 코드의 대부분은 이해가 될 것이지만, 언급하지 않은 부분이 한 가지 있다. 바로, line24)에 있는 조건문중 하나인, checkWall() 함수이다. 온풍기의 바람이 퍼져나갈 때, 벽의 위치에 따른 조건이 문제에 제시되어 있다.
그 부분을 구현한 내용인데 매우 머리에 쥐가 날 것처럼 헷갈리는 부분이지만, 어떻게 설명을 해야할지를 잘 모르겠다.
먼저 코드부터 보고 난 후에 이야기를 해보자. 코드를 하나하나 이해하려 하지말고 그냥 얼핏 보고 넘어가자.
bool checkWall(int x, int y, int nx, int ny, int d, int dir) {
if (dir == 1) {
if (wallMap[x][y][d] == false) return true;
}
else if(dir == 0){
if (d == 0) {
int upx = x - 1;
int upy = y;
if (wallMap[x][y][3] == false && wallMap[upx][upy][0] == false) return true;
}
else if (d == 1) {
int upx = x - 1;
int upy = y;
if (wallMap[x][y][3] == false && wallMap[upx][upy][1] == false) return true;
}
else if (d == 2) {
int dnx = x;
int dny = y - 1;
if (wallMap[x][y][1] == false && wallMap[dnx][dny][2] == false) return true;
}
else if (d == 3) {
int dnx = x;
int dny = y - 1;
if (wallMap[x][y][1] == false && wallMap[dnx][dny][3] == false) return true;
}
}
else if (dir == 2) {
if (d == 0) {
int upx = x + 1;
int upy = y;
if (wallMap[x][y][2] == false && wallMap[upx][upy][0] == false) return true;
}
else if (d == 1) {
int upx = x + 1;
int upy = y;
if (wallMap[x][y][2] == false && wallMap[upx][upy][1] == false) return true;
}
else if (d == 2) {
int dnx = x;
int dny = y + 1;
if (wallMap[x][y][0] == false && wallMap[dnx][dny][2] == false) return true;
}
else if (d == 3) {
int dnx = x;
int dny = y + 1;
if (wallMap[x][y][0] == false && wallMap[dnx][dny][3] == false) return true;
}
}
return false;
}위의 함수에서 매개변수 중, 'd'는 온풍기에서 나오는 바람의 방향을 의미하고, 'dir'은 3칸 중 어느 칸으로 나아갈지를 나타내는 부분이다 .여기서 '3칸'은 위에서 이야기했듯이, 바람이 점점 퍼지면서 나아가기 때문에, 모든 좌표에서 3칸씩 화살표를 뻗으면서 나아간다고 이야기 했었다. 그리고 그 과정에서 업데이트가 중복되지 않도록 만들어주는 것도 이야기를 했었다.
여기서 그 3칸을 의미한다.
먼저, dir = 1 인 경우 온풍기의 바람이 대각선이 아닌 나오는 바람 방향 그대로 직진하는 경우를 의미한다.
그대로 직진하는 경우에는 현재 칸과, 그 다음 칸 사이에 벽이 있는지만 확인을 해주면 된다.
그렇기에, line3)의 조건문이 저렇게 구현되는 것이다.
이제, 남은 것은 바람이 대각선으로 나오는 경우들인데, 이 경우에는 문제에서 제시한대로, 현재 칸의 옆칸과 바람이 향하는 칸 사이에 있는 벽들을 고려를 해주어야 한다. 그 벽들을 고려해주는 것이 위의 코드에서 남은 부분들이다.
코드의 양도 꽤 되는 것 같고, 뭔가 구현도 많이 되어 있는 것 같은데 사실 어떻게 설명을 해야할지 잘 모르겠다.
사람마다 방향을 나타내는 값을 설정하는 것도 모두 다르기 때문에 위의 설정되어 있는 Index값 하나하나를 설명하는 것은 크게 의미가 없는 것이라고 생각한다. 무튼 ! 본인은 위와 같이 벽을 판단해 주고 false가 return 된다면, 벽에 가로막혀서 바람이 갈 수 없으니 탐색을 해주지 않았다.
#3. 2번과정 - 바람의 양 조절하기
모든 칸에 대해서, 서로 인접한 칸과 비교를 해서 온도가 조절되는 과정이다.
서로 인접한 칸이라는 것은, 하나의 좌표를 기준으로 상, 하, 좌, 우 에 있는 4개의 칸을 의미한다.
그리고 이 과정은 "모든 칸에 대해서 동.시.에 발생한다" 라고 되어 있다.
문제에서는 상/하/좌/우 4개의 있는 칸을 비교해서 온도를 조절하라고 했지만, 본인은 우/하 즉, 동쪽과 남쪽에 있는 2개의 좌표랑만 비교를 해서 온도를 조절해 주었다. 왜그럴까 ?!
아래의 예시를 한번 살펴보자.
가장 먼저, 빨강색 칸을 기준으로 온도를 조절하는 과정을 진행해보자. 그렇게되면, 인접한 칸인 2개의 파랑색 칸에 대해서 계산을 진행하게 될 것이다. 빨강색 칸을 기준으로 북쪽과 서쪽에는 칸이 존재하지 않기 때문에 비교를 할 수 없을 것이다.
그럼, 파랑색칸들과 빨강색 칸을 비교해서 뭐 어떻게 온도가 조절되었다고 가정해보자.
그리고 그 다음, '10'의 값을 가지고 있는 파랑색 칸을 기준으로 온도를 조절하는 과정을 진행해보자.
빨강색 칸을 기준으로 북쪽에는 칸이 없기 때문에 서쪽과 남쪽 그리고 동쪽 3개의 파랑색 칸에 대해서 온도 조절을 실행하게 될 것이다. 그런데 ! 왼쪽에 있는 '5'와의 관계에 대해서 한번 생각을 해보자.
분명, 이전에 '5'가 중심일 때, '10'과 비교를 해서 온도조절을 한 적이 있다. 그런데 ! 여기서 또 한번 '10'과 '5'를 비교를 해서 온도조절을 해야 하는 상황이 발생하게 된다. 왜 이런 상황이 발생했을까 ??
지금 탐색하는 순서가, 주어진 맵을 하나의 행에서 열부터 모두 탐색을 하고, 그 다음 행으로 탐색을 하는 순서대로 탐색을 진행하고 있기 때문이다. 즉 ! (0 , 0)부터 (R , C)까지 순차적으로 탐색을 하게 된다면, 서쪽과 북쪽에 대해서는 온도조절을 할 필요가 없다. 왜냐하면 기존에 이미 온도조절을 했기 때문이다. 현재 좌표를 (x , y) 그리고 서쪽에 있는 좌표를 (x - 1 , y)로 둔다면, 이 2개의 좌표에 대한 온도조절은, (x - 1 , y)에서 남쪽 방향에 있는 (x , y)와 온도조절을 할 때 이미 온도조절을 했기 때문에, 굳이 (x , y)에서 (x - 1, y)와 한번 더 온도 조절을 해줄 필요가 없다는 것이다.
그렇기 때문에 ! 본인은 맵을 (0 , 0)부터 (R , C)까지 순차적으로 탐색을 하고, 그 과정에서 인접한 칸에 대한 온도조절은 동쪽과 남쪽에 대해서만 진행을 해 주었다. 그리고 또 하나 중요한 것은, 이러한 과정은 모든칸에 대해서 "동시에" 일어난다는 것이다.
위의 경우에서 가장 왼쪽위에 있는 '5'와 빨강색으로 표시되어 있는 '10' 사이에서 온도조절이 발생하게 된다면, (10 - 5 ) / 4 만큼 값이 바뀌게 되므로, 가장 왼쪽위에 있는 '5'는 '6'으로 빨강색으로 표시되어 있는 '10'은 '9'가 될 것이다.
이후에 , 빨강색으로 표시되어 있는 '10'과 그 오른쪽에 있는 '15'가 계산이 일어나는 순간을 생각해보자.
이미, 빨강색 좌표는 '9'로 온도가 낮아졌지만, 문제에서는 "모든 칸에 대해서 동시에 일어난다"고 했으므로, 사실 계산은 10과 15로 해 주어야 한다는 것이다. 그렇기 때문에, 본인은 "온도 변화의 가중치를 저장해주는 임의의 맵"을 하나 만들어서 계산해 주었다. 그리고 모든 계산을 끝낸 후에는 원래의 맵에다가 온도조절에 의해서 발생한 가중치 만큼을 더해주었다.
이에 해당하는 소스코드는 다음과 같다.
void controlTemperature() {
int tempMap[MAX][MAX] = { 0, };
for (int x = 1; x <= r; x++) {
for (int y = 1; y <= c; y++) {
for (int i = 0; i < 2; i++) {
int dir = i == 0 ? 0 : 2;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 1 && ny >= 1 && nx <= r && ny <= c) {
if (wallMap[x][y][dir] == false) {
pair<int, int> maxCoord, minCoord;
if (map[x][y] > map[nx][ny]) {
maxCoord = { x, y };
minCoord = { nx, ny };
}
else {
maxCoord = { nx, ny };
minCoord = { x, y };
}
int diff = abs(map[x][y] - map[nx][ny]);
diff /= 4;
tempMap[maxCoord.first][maxCoord.second] -= diff;
tempMap[minCoord.first][minCoord.second] += diff;
}
}
}
}
}
addMap(map, tempMap);
}
#4. 가장 바깥쪽 온도 감소 & 정답도출
먼저, 가장 바깥족 온도를 감소시키는 과정은 매우 간단하다. 말 그대로, 가장 바깥쪽에 해당하는 좌표들 중에서 온도가 1 이상인 좌표들은 온도를 1씩 감소시켜 주면 된다. 특별한 방법이 사용된 것이 아니기 때문에 그냥 소스코드로 설명을 대체하겠다.
그리고, 최종적으로 정답을 도출해 주어야 하는데, 이 또한 입력할 때 받아두었던 "조사해야 하는 칸들을 저장해 놓은 구현체를 탐색하면서 모두 온도가 K 이상인지 확인"만 해주면 된다.
[ 소스코드 ]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
#include <iostream>
#include <vector>
#include <queue>
#define endl "\n"
#define MAX 25
using namespace std;
int r, c, k, w;
int map[MAX][MAX];
bool wallMap[MAX][MAX][4];
vector<pair<int, int>> searchPos;
vector<pair<pair<int, int>, int>> heater;
vector<pair<pair<int, int>, int>> wall;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int wdx[4][3] = { { -1, 0, 1 }, {-1, 0, 1 }, {1, 1, 1}, {-1, -1, -1} };
int wdy[4][3] = { { 1, 1, 1}, { -1, -1, -1 }, {-1, 0, 1 },{-1, 0, 1} };
void printMap(int A[][MAX]) {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
printf("%2d ", A[i][j]);
}
cout << endl;
}
cout << "#######################################################" << endl;
}
void input() {
cin >> r >> c >> k;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> map[i][j];
if (map[i][j] != 0 && map[i][j] != 5) {
heater.push_back(make_pair(make_pair(i, j), map[i][j]));
}
else if (map[i][j] == 5) {
searchPos.push_back(make_pair(i, j));
}
map[i][j] = 0;
}
}
cin >> w;
for (int i = 0; i < w; i++) {
int a, b, c; cin >> a >> b >> c;
wall.push_back(make_pair(make_pair(a, b), c));
}
}
void settingWall() {
for (int i = 0; i < w; i++) {
int x = wall[i].first.first;
int y = wall[i].first.second;
int t = wall[i].second;
if (t == 0) {
wallMap[x][y][3] = true;
wallMap[x - 1][y][2] = true;
}
else {
wallMap[x][y][0] = true;
wallMap[x][y + 1][1] = true;
}
}
}
bool check() {
for (int i = 0; i < searchPos.size(); i++) {
int x = searchPos[i].first;
int y = searchPos[i].second;
if (map[x][y] < k) return false;
}
return true;
}
int changeMydir(int d) {
switch (d) {
case 1:
return 0;
case 2:
return 1;
case 3:
return 3;
case 4:
return 2;
}
}
void copyMap(int A[][MAX], int B[][MAX]) {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
A[i][j] = B[i][j];
}
}
}
bool checkWall(int x, int y, int nx, int ny, int d, int dir) {
if (dir == 1) {
if (wallMap[x][y][d] == false) return true;
}
else if(dir == 0){
if (d == 0) {
int upx = x - 1;
int upy = y;
if (wallMap[x][y][3] == false && wallMap[upx][upy][0] == false) return true;
}
else if (d == 1) {
int upx = x - 1;
int upy = y;
if (wallMap[x][y][3] == false && wallMap[upx][upy][1] == false) return true;
}
else if (d == 2) {
int dnx = x;
int dny = y - 1;
if (wallMap[x][y][1] == false && wallMap[dnx][dny][2] == false) return true;
}
else if (d == 3) {
int dnx = x;
int dny = y - 1;
if (wallMap[x][y][1] == false && wallMap[dnx][dny][3] == false) return true;
}
}
else if (dir == 2) {
if (d == 0) {
int upx = x + 1;
int upy = y;
if (wallMap[x][y][2] == false && wallMap[upx][upy][0] == false) return true;
}
else if (d == 1) {
int upx = x + 1;
int upy = y;
if (wallMap[x][y][2] == false && wallMap[upx][upy][1] == false) return true;
}
else if (d == 2) {
int dnx = x;
int dny = y + 1;
if (wallMap[x][y][0] == false && wallMap[dnx][dny][2] == false) return true;
}
else if (d == 3) {
int dnx = x;
int dny = y + 1;
if (wallMap[x][y][0] == false && wallMap[dnx][dny][3] == false) return true;
}
}
return false;
}
void addMap(int A[][MAX], int B[][MAX]) {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
A[i][j] += B[i][j];
}
}
}
void spread(int x, int y, int d) {
bool update[MAX][MAX] = { false, };
d = changeMydir(d);
x += dx[d];
y += dy[d];
if (x < 1 || y < 1 || x > r || y > c) return;
queue<pair<pair<int, int>, int >> q;
q.push(make_pair(make_pair(x, y), 5));
while (q.empty() == 0) {
int x = q.front().first.first;
int y = q.front().first.second;
int wind = q.front().second;
q.pop();
map[x][y] += wind;
if (wind == 1) continue;
for (int i = 0; i < 3; i++) {
int nx = x + wdx[d][i];
int ny = y + wdy[d][i];
if (nx >= 1 && ny >= 1 && nx <= r && ny <= c) {
if (update[nx][ny] == false && checkWall(x, y, nx, ny, d, i) == true) {
update[nx][ny] = true;
q.push(make_pair(make_pair(nx, ny), wind - 1));
}
}
}
}
}
void spreadWind() {
for (int i = 0; i < heater.size(); i++) {
int x = heater[i].first.first;
int y = heater[i].first.second;
int d = heater[i].second;
spread(x, y, d);
}
}
void controlTemperature() {
int tempMap[MAX][MAX] = { 0, };
for (int x = 1; x <= r; x++) {
for (int y = 1; y <= c; y++) {
for (int i = 0; i < 2; i++) {
int dir = i == 0 ? 0 : 2;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 1 && ny >= 1 && nx <= r && ny <= c) {
if (wallMap[x][y][dir] == false) {
pair<int, int> maxCoord, minCoord;
if (map[x][y] > map[nx][ny]) {
maxCoord = { x, y };
minCoord = { nx, ny };
}
else {
maxCoord = { nx, ny };
minCoord = { x, y };
}
int diff = abs(map[x][y] - map[nx][ny]);
diff /= 4;
tempMap[maxCoord.first][maxCoord.second] -= diff;
tempMap[minCoord.first][minCoord.second] += diff;
}
}
}
}
}
addMap(map, tempMap);
}
void decreaseTemperature() {
for (int i = 1; i <= c; i++) {
if (map[1][i] > 0) map[1][i]--;
if (map[r][i] > 0) map[r][i]--;
}
for (int i = 2; i < r; i++) {
if (map[i][1] > 0) map[i][1]--;
if (map[i][c] > 0) map[i][c]--;
}
}
void solution() {
settingWall();
int chocolate = 0;
while (1) {
if (chocolate > 100) {
break;
}
spreadWind();
controlTemperature();
decreaseTemperature();
chocolate++;
if (check() == true) {
break;
}
}
cout << chocolate << endl;
}
void solve() {
input();
solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
solve();
return 0;
}
|
cs |