백준 23289 온풍기 안녕!

https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

 

문제

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정을 설명하면 다음과 같다.

<그림 1>

<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다. 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다. 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가하게 된다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 해당하는 방향으로 바람이 나왔을 때 증가하는 온도를 구할 수 있다.

<그림 2>

온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동해 다른 칸의 온도를 위의 그림과 같이 상승시키게 된다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 상승했다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 상승하게 된다. 이때 그 칸이 존재하지 않는다면, 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착한다고 해도 온도는 여러번 상승하지 않는다.

<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 <그림 3>과 같다.

<그림 3>

일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.

예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있는 경우 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 상승한다. 벽은 빨간색으로 표시했다.

<그림 4>

(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 상승하지 않는다.

만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있는 경우라면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 상승한다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우이다.

 

구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.

예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.

온도가 조절되는 과정은 다음과 같다.

모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.

다음은 온도 조절의 예시이다.

(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.

(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.

모든 칸에 대해서 동시에 온도의 조절이 발생한다.

가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.

방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.

입력

첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.

• 0: 빈 칸
• 1: 방향이 오른쪽인 온풍기가 있음
• 2: 방향이 왼쪽인 온풍기가 있음
• 3: 방향이 위인 온풍기가 있음
• 4: 방향이 아래인 온풍기가 있음
• 5: 온도를 조사해야 하는 칸

다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.

출력

구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.

제한

• 2 ≤ R, C ≤ 20
• 1 ≤ K ≤ 1,000
• 온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
• 0 ≤ W ≤ R×C
• 1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
• 1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
• 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
• 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
• 같은 벽이 두 번 이상 주어지는 경우는 없다.

예제 입력 1 복사

7 8 1
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 1 복사

1

---

[풀이 과정]

1. 주어진 격자판 정보를 arr배열에 입력 받고 1~4의 값은 heater 벡터에 {x, y, type} 구조체로 담았고, 5의 경우 K이상인지 확인할 곳이기에 target벡터에 {x, y} 위치를 저장했다. 주어진 인덱스는 (1, 1)부터였지만 (0, 0)으로 문제푸는 것을 선호해서 기준을 (0, 0)으로 잡았다. arr배열은 이후 온도를 저장할 배열이기에 입력을 받은 후 0으로 초기화한다.

 

2. W를 입력받고 W개의 벽 정보를 입력 받는다. 위에서 (0, 0)으로 시작하게 만들었기 때문에 벽 위치도 -1 씩 해준다.

벽 정보는 wall 벡터에 저장하는데 (x, y)와 (x-1, y) 사이에 벽이면 벡터에 1을 저장하고, (x, y)와 (x, y+1) 사이에 벽이 있는 경우엔 2를 저장했다. 

 

3. 초콜릿의 개수가 100을 넘을 때까지 start_heater(), control_temp(), reduce_temp()함수를 반복한다.

각 사이클마다 check()함수를 실행시켜 target의 위치들이 모두 K가 넘었는지 확인한다.

 

4. start_heater(int type, int x, int y)- type : 온풍기 종류<type 1>

- 1번의 경우 바람이 오른쪽으로 나가는 온풍기이다. 따라서 온풍기의 위치인 (x, y)의 바로 오른쪽 칸인 (x, y+1)에 먼저 5를 더해주고 방문 표시를 했고 q에 넣어서 탐색을 시작한다.

- q가 빌 때까지 진행하는데 온도는 5~1까지 퍼지게 되므로 ct가 0일 땐 더이상 탐색을 진행하지 않고 종료한다.

- (cx, cy)가 범위를 벗어난 경우에도 종료한다.

 

- 이제부터 <type 1> 그림의 1, 2, 3에 대한 코드이다.

1) 1번처럼 바람이 퍼지기 위해서는 (cx - 1, cy + 1)이 격자판 안에 있어야 하며 방문 전이어야 한다. 

    (이때 방문 처리를 하지 않으면 나중에 중복으로 바람이 퍼질 수 있다.) 

    범위와 방문여부를 판단했으면 벽의 유무를 판단해야 한다. 

    1번의 경우 두 벽 중 하나라도 있으면 바람이 퍼질 수 없다. 따라서 wall 벡터의 (cx - 1, y) 칸에 오른쪽 벽이 있는지,

    (cx, cy) 칸에 위쪽. 벽이 있는지를 확인해야 한다.

    위 조건을 통과하면 바람이 퍼질 수 있기 때문에 arr[cx - 1][cy + 1]칸에 ct - 1 을 더하고 방문 표시 후 다음 탐색을 위해 q에 넣는다.

 

2) 2번처럼 바람이 퍼지기 위해서는 (cx, cy + 1)이 격자판 안에 있어야 하며 방문 전이어야 한다.

    2의 경우엔 (cx, cy) 칸에 오른쪽 벽이 있는지만 확인하면 된다.

    위 조건을 통과하면 바람이 퍼질 수 있기 때문에 arr[cx][cy + 1] 칸에 ct - 1 을 더하고 방문 표시 후 다음 탐색을 위해 q에 넣는다.

 

3) 3번처럼 바람이 퍼지기 위해서는 (cx + 1, cy + 1)이 격자판 안에 있어야 하며 방문 전이어야 한다.

    두 개의 벽 모두 wall 벡터의 (cx + 1, cy)에 저장되어 있으므로 wall[cx + 1][cy].size()가 0인지 확인한다.

    위 조건을 통과하면 바람이 퍼질 수 있기 때문에 arr[cx + 1][cy + 1] 칸에 ct - 1 을 더하고 방문 표시 후 다음 탐색을 위해 q에 넣는다.

 

 

type 2, 3, 4 도 같은 방식으로 구현하면 된다.

 

5. control_temp() : 온도를 조절 함수

- 모든 곳에서 동시에 온도 조절이 일어나기 때문에 임시 배열에 온도 변화에 대해 저장 후 한꺼번에 적용한다. (arr 배열에 바로 온도 변화를 적용시키면 이후 값들에 모두 영향을 주기 때문이다.)

- 여기서는 방향을 0(오른쪽), 1(아래쪽)에 대해서만 탐색을 했는데 그 이유는 상하좌우 4방향에 대해 온도를 비교할 경우 중복되는 경우가 발생해 방문처리를 해줘야 한다. 이 부분을 생략하기 위해 방향 0, 1에 대해서만 온도 비교를 했다.

 

- 방향 0, 1에 대해 다음 위치가 격자판 내에 있고 0의 경우 오른쪽 벽이 있으면 continue, 1의 경우 위쪽 벽이 있으면 continue를 했다.

- 벽이 없다면 현재 위치의 온도인 arr[i][j]와 다음 위치인 arr[nx][ny]의 값을 비교했고 (두 값의 차이 / 4)만큼 더해주는 것, 빼주는 것은 tmp 배열에 저장해두었다. (위에서 설명한 내용, 동시에 온도 조절을 위해)

- 모든 격자판에 대해 온도 조절이 됐으면 전체 tmp를 arr 배열에 더해서 적용시킨다.

 

6. reduce_temp() : 온도가 1 이상인 가장 바깥쪽 칸의 온도를 1씩 감소시키는 함수

- 테두리에 대해 0보다 큰 값이면 -1 씩 해준다.

 

7. check() : target값들이 K가 넘었는지 확인하는 함수

- target벡터의 값들을 가지고 해당 위치 중 하나라도 K보다 작으면 false를 리턴한다.

- 모든 위치에 대해 K보다 크면 true를 리턴한다.

 

8. check_range(int x, int y) : 해당 (x, y)가 격자판 안에 위치했는지 확인하는 함수

- 격자판 내에 있다면 true 리턴한다.

- 격자판 밖에 있다면 false 리턴한다.

 

9. 마지막으로 chocolate값을 출력하면 된다.

    

---

[소스 코드]

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 25;

int R, C, K, W, arr[MAX][MAX], tmp[MAX][MAX], x, y, t;
vector <int> wall[MAX][MAX];
bool visited[MAX][MAX];
struct INFO{
    int x, y, type;
};
struct Q_INFO{
    int x, y, temp;
};
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
vector <INFO> heater;
vector <pair<int, int>> target;

bool check_range(int x, int y){
    if(x < 0 || x >= R || y < 0 || y >= C) return false;
    else return true;
}

void start_heater(int type, int x, int y){
    memset(visited, 0, sizeof(visited));
    queue <Q_INFO> q;

    if(type == 1){
        arr[x][y+1] += 5;
        visited[x][y+1] = true;
        q.push({x, y+1, 5});

        while(!q.empty()){
            int cx = q.front().x;
            int cy = q.front().y;
            int ct = q.front().temp;
            q.pop();

            if(ct == 0) break;
            if(!check_range(cx, cy)) continue;

            if(check_range(cx-1, cy+1) && !visited[cx-1][cy+1]) {
                if(check_range(cx-1, y) && (wall[cx-1][cy].size() == 0 || (wall[cx-1][cy].size() == 1 && wall[cx-1][cy].front() != 2))){
                    if(wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 1)){
                        arr[cx - 1][cy + 1] += ct - 1;
                        visited[cx - 1][cy + 1] = true;
                        q.push({cx - 1, cy + 1, ct - 1});
                    }
                }
            }

            if (check_range(cx, cy + 1) && !visited[cx][cy+1]) {
                if (wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 2)) {
                    arr[cx][cy + 1] += ct - 1;
                    visited[cx][cy + 1] = true;
                    q.push({cx, cy + 1, ct - 1});
                }
            }

            if(check_range(cx+1, cy+1) && !visited[cx+1][cy+1]){
                if(check_range(cx+1, cy) && wall[cx+1][cy].size() == 0){
                    arr[cx+1][cy+1] += ct-1;
                    visited[cx+1][cy+1] = true;
                    q.push({cx+1, cy+1, ct-1});
                }
            }
        }
    }
    else if(type == 2){
        arr[x][y-1] += 5;
        visited[x][y-1] = true;
        q.push({x, y-1, 5});

        while(!q.empty()){
            int cx = q.front().x;
            int cy = q.front().y;
            int ct = q.front().temp;
            q.pop();

            if(ct == 0) break;
            if(!check_range(cx, cy)) continue;

            if(check_range(cx-1, cy-1) && !visited[cx-1][cy-1]) {
                if(wall[cx-1][cy-1].size() == 0 || (wall[cx-1][cy-1].size() == 1 && wall[cx-1][cy-1].front() != 2)){
                    if(wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 1)){
                        arr[cx - 1][cy - 1] += ct - 1;
                        visited[cx - 1][cy - 1] = true;
                        q.push({cx - 1, cy - 1, ct - 1});
                    }
                }
            }
            if(check_range(cx, cy-1) && !visited[cx][cy-1]){
                if(wall[cx][cy-1].size() == 0 || (wall[cx][cy-1].size() == 1 && wall[cx][cy-1].front() != 2)){
                    arr[cx][cy-1] += ct-1;
                    visited[cx][cy-1] = true;
                    q.push({cx, cy-1, ct-1});
                }
            }
            if(check_range(cx+1, cy-1) && !visited[cx+1][cy-1]) {
                if (check_range(cx + 1, cy) && (wall[cx + 1][cy].size() == 0 || (wall[cx + 1][cy].size() == 1 && wall[cx + 1][cy].front() != 1))) {
                    if (wall[cx + 1][cy - 1].size() == 0 || (wall[cx + 1][cy - 1].size() == 1 && wall[cx + 1][cy - 1].front() != 2)) {
                        arr[cx + 1][cy - 1] += ct - 1;
                        visited[cx + 1][cy - 1] = true;
                        q.push({cx + 1, cy - 1, ct - 1});
                    }
                }
            }
        }
    }
    else if(type == 3){
        arr[x-1][y] += 5;
        visited[x-1][y] = true;
        q.push({x-1, y, 5});

        while(!q.empty()){
            int cx = q.front().x;
            int cy = q.front().y;
            int ct = q.front().temp;
            q.pop();

            if(ct == 0) break;
            if(!check_range(cx, cy)) continue;

            if(check_range(cx-1, cy-1) && !visited[cx-1][cy-1]) {
                if (check_range(cx, cy - 1) && wall[cx][cy - 1].size() == 0) {
                    arr[cx - 1][cy - 1] += ct - 1;
                    visited[cx - 1][cy - 1] = true;
                    q.push({cx - 1, cy - 1, ct - 1});
                }
            }
            if(check_range(cx-1, cy) && !visited[cx-1][cy]) {
                if (wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 1)) {
                    arr[cx - 1][cy] += ct - 1;
                    visited[cx - 1][cy] = true;
                    q.push({cx - 1, cy, ct - 1});
                }
            }
            if(check_range(cx-1, cy+1) && !visited[cx-1][cy+1]){
                if (check_range(cx, cy + 1) && (wall[cx][cy + 1].size() == 0 || (wall[cx][cy + 1].size() == 1 && wall[cx][cy + 1].front() != 1))) {
                    if (wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 2)) {
                        arr[cx - 1][cy + 1] += ct - 1;
                        visited[cx - 1][cy + 1] = true;
                        q.push({cx - 1, cy + 1, ct - 1});
                    }
                }
            }
        }
    }
    else {
        arr[x+1][y] += 5;
        visited[x+1][y] = true;
        q.push({x+1, y, 5});

        while(!q.empty()){
            int cx = q.front().x;
            int cy = q.front().y;
            int ct = q.front().temp;
            q.pop();

            if(ct == 0) break;
            if(!check_range(cx, cy)) continue;

            if(check_range(cx+1, cy-1) && !visited[cx+1][cy-1]) {
                if (check_range(cx, cy-1) && (wall[cx][cy - 1].size() == 0 || (wall[cx][cy-1].size() == 1 && wall[cx][cy-1].front() != 2))) {
                    if(wall[cx+1][cy-1].size() == 0 || (wall[cx+1][cy-1].size() == 1 && wall[cx+1][cy-1].front() != 1)) {
                        arr[cx + 1][cy - 1] += ct - 1;
                        visited[cx + 1][cy - 1] = true;
                        q.push({cx + 1, cy - 1, ct - 1});
                    }
                }
            }
            if(check_range(cx+1, cy) && !visited[cx+1][cy]){
                if((wall[cx+1][cy].size() == 0 || (wall[cx+1][cy].size() == 1 && wall[cx+1][cy].front() != 1))){
                    arr[cx+1][cy] += ct-1;
                    visited[cx+1][cy] = true;
                    q.push({cx+1, cy, ct-1});
                }
            }
            if(check_range(cx+1, cy+1) && !visited[cx+1][cy+1]) {
                if(wall[cx][cy].size() == 0 || (wall[cx][cy].size() == 1 && wall[cx][cy].front() != 2)) {
                    if(wall[cx+1][cy+1].size() == 0 || (wall[cx+1][cy+1].size() == 1 && wall[cx+1][cy+1].front() != 1)){
                        arr[cx + 1][cy + 1] += ct - 1;
                        visited[cx + 1][cy + 1] = true;
                        q.push({cx + 1, cy + 1, ct - 1});
                    }
                }
            }
        }
    }
}

void control_temp(){
    memset(tmp, 0, sizeof(tmp));
    for(int i=0;i<R;i++) {
        for (int j = 0; j < C; j++) {
            for (int d = 0; d < 2; d++) {
                int nx = i + dx[d];
                int ny = j + dy[d];

                if (check_range(nx, ny)) {
                    if (d == 0) {
                        if (wall[i][j].size() == 2) continue;
                        else if (wall[i][j].size() == 1 && wall[i][j].front() == 2) continue;
                    }
                    else if (d == 1) {
                        if (wall[nx][ny].size() == 2) continue;
                        else if (wall[nx][ny].size() == 1 && wall[nx][ny].front() == 1) continue;
                    }
                    if (arr[i][j] > arr[nx][ny]) {
                        int val = (arr[i][j] - arr[nx][ny]) / 4;
                        tmp[i][j] -= val;
                        tmp[nx][ny] += val;
                    }
                    else if(arr[i][j] < arr[nx][ny]){
                        int val = (arr[nx][ny] - arr[i][j]) / 4;
                        tmp[i][j] += val;
                        tmp[nx][ny] -= val;
                    }
                }
            }
        }
    }
    for(int i=0;i<R;i++) {
        for (int j = 0; j < C; j++) {
            arr[i][j] += tmp[i][j];
        }
    }
}

bool check(){
    bool flag = true;

    for(int i=0;i<target.size();i++){
        int x = target[i].first;
        int y = target[i].second;
        if(arr[x][y] < K) {
            flag = false;
            break;
        }
    }
    return flag;
}

void reduce_temp(){
    for(int i=0;i<R;i++){
        if(arr[i][0] > 0) arr[i][0]--;
        if(arr[i][C-1] > 0) arr[i][C-1]--;
    }
    for(int j=1;j<C-1;j++){
        if(arr[0][j] > 0) arr[0][j]--;
        if(arr[R-1][j] > 0) arr[R-1][j]--;
    }
}

int main(){
    scanf("%d %d %d", &R, &C, &K);

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            scanf("%d", &arr[i][j]);
            if(arr[i][j] > 0 && arr[i][j] < 5) {
                heater.push_back({i, j, arr[i][j]});
                arr[i][j] = 0;
            }
            else if (arr[i][j] == 5) {
                target.push_back({i, j});
                arr[i][j] = 0;
            }
        }
    }

    scanf("%d", &W);

    for(int i=0;i<W;i++){
        scanf("%d %d %d", &x, &y, &t);
        x--; y--;

        if(t == 0) wall[x][y].push_back(1);
        else wall[x][y].push_back(2);
    }

    int chocolate = 0;

    while(1){
        if(chocolate > 100) break;
        for(int i=0;i<heater.size();i++) start_heater(heater[i].type, heater[i].x, heater[i].y);
        control_temp();
        reduce_temp();
        chocolate++;
        if(check()) break;
    }
    printf("%d\n", chocolate);
    return 0;
}