온풍기 안녕! C++

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

23289번: 온풍기 안녕!

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int MAX = 25;
int r, c, k;
int map[MAX][MAX];
int tmp_map[MAX][MAX];
int wall[MAX][MAX][4]; // 0:위, 1:아래, 2:오른쪽, 3:왼쪽
struct INFO { int x, y, dir; };
vector<INFO> wind;
vector<pair<int, int>> searchs;
int answer = 0;
int visited[MAX][MAX]; 
void MoveR(int mi, int mj, int value) {
 queue<INFO> q;
 q.push({ mi,mj,value });
 while (!q.empty()) {
  int ii = q.front().x;
  int jj = q.front().y;
  int v = q.front().dir;
  q.pop();
  if (v <= 0) continue;
  if (ii - 1 >= 1 && jj + 1 <= c) {
   if (visited[ii - 1][jj + 1] == -1) {
    if (wall[ii][jj][0] != 1 && wall[ii - 1][jj][2] != 1) {
     tmp_map[ii - 1][jj + 1] += v;
     visited[ii - 1][jj + 1] = 1;
     q.push({ ii - 1,jj + 1,v - 1 });
    }
   }
  }
  if (jj + 1 <= c) {
   if (visited[ii][jj + 1] == -1) {
    if (wall[ii][jj][2] != 1) {
     tmp_map[ii][jj + 1] += v;
     visited[ii][jj + 1] = 1;
     q.push({ ii,jj + 1,v - 1 });
    }
   }
  }
  if (ii + 1 <= r && jj + 1 <= c) {
   if (visited[ii + 1][jj + 1] == -1) {
    if (wall[ii+1][jj][0] != 1 && wall[ii + 1][jj][2] != 1) {
     tmp_map[ii + 1][jj + 1] += v;
     visited[ii + 1][jj + 1] = 1;
     q.push({ ii + 1,jj + 1,v - 1 });
    }
   }
  }
 }
}
void MoveL(int mi, int mj, int value) {
 queue<INFO> q;
 q.push({ mi,mj,value });
 while (!q.empty()) {
  int ii = q.front().x;
  int jj = q.front().y;
  int v = q.front().dir;
  q.pop();
  if (v <= 0) continue;
  if (ii - 1 >= 1 && jj - 1 >= 1) {
   if (visited[ii - 1][jj - 1] == -1) {
    if (wall[ii][jj][0] != 1 && wall[ii - 1][jj - 1][2] != 1) {
     tmp_map[ii - 1][jj - 1]+= v;
     visited[ii - 1][jj - 1] = 1;
     q.push({ii - 1, jj - 1, v - 1 });
    }
   }
  }
  if (jj - 1 >= 1) {
   if (visited[ii][jj - 1] == -1) {
    if (wall[ii][jj-1][2] != 1) {
     tmp_map[ii][jj - 1]+= v;
     visited[ii][jj - 1] = 1;
     q.push({ ii, jj - 1, v - 1 });
    }
   }
  }
  if (ii + 1 <= r && jj - 1 >= 1) {
   if (visited[ii + 1][jj - 1] == -1) {
    if (wall[ii+1][jj][0] != 1 && wall[ii + 1][jj - 1][2] != 1) {
     tmp_map[ii + 1][jj - 1]+= v;
     visited[ii + 1][jj - 1] = 1;
     q.push({ ii + 1, jj - 1, v - 1 });
    }
   }
  }
 }
}
void MoveU(int mi, int mj, int value) {
 queue<INFO> q;
 q.push({ mi,mj,value });
 while (!q.empty()) {
  int ii = q.front().x;
  int jj = q.front().y;
  int v = q.front().dir;
  q.pop();
  if (v <= 0) continue;
  if (ii - 1 >= 1 && jj + 1 <= c) {
   if (visited[ii - 1][jj + 1] == -1) {
    if (wall[ii][jj][2] != 1 && wall[ii][jj+1][0] != 1) {
     tmp_map[ii - 1][jj + 1] += v;
     visited[ii - 1][jj + 1] = 1;
     q.push({ ii - 1, jj + 1, v - 1 });
    }
   }
  }
  if (ii - 1 >= 1) {
   if (visited[ii - 1][jj] == -1) {
    if (wall[ii][jj][0] != 1) {
     tmp_map[ii - 1][jj]+= v;
     visited[ii - 1][jj] = 1;
     q.push({ ii - 1, jj, v - 1});
    }
   }
  }
  if (ii - 1 >= 1 && jj - 1 >= 1) {
   if (visited[ii - 1][jj - 1] == -1) {
    if (wall[ii][jj-1][2] != 1 && wall[ii][jj - 1][0] != 1) {
     tmp_map[ii - 1][jj - 1]+= v;
     visited[ii - 1][jj - 1] = 1;
     q.push({ ii - 1, jj - 1, v - 1 });
    }
   }
  }
 }
}
// 0:위, 1:아래, 2:오른쪽, 3:왼쪽
void MoveD(int mi, int mj, int value) {
 queue<INFO> q;
 q.push({ mi,mj,value });
 while (!q.empty()) {
  int ii = q.front().x;
  int jj = q.front().y;
  int v = q.front().dir;
  q.pop();
  if (v <= 0) continue;
  if (ii + 1 <= r && jj - 1 >= 1) {
   if (visited[ii + 1][jj - 1] == -1) {
    if (wall[ii][jj-1][2] != 1 && wall[ii+1][jj - 1][0] != 1) {
     tmp_map[ii + 1][jj - 1]+= v;
     visited[ii + 1][jj - 1] = 1;
     q.push({ ii + 1, jj - 1, v - 1 });
    }
   }
  }
  if (ii + 1 <= r) {
   if (visited[ii + 1][jj] == -1) {
    if (wall[ii+1][jj][0] != 1) {
     tmp_map[ii + 1][jj]+= v;
     visited[ii + 1][jj] = 1;
     q.push({ ii + 1, jj, v - 1 });
    }
   }
  }
  if (ii + 1 <= r && jj + 1 <= c) {
   if (visited[ii + 1][jj + 1] == -1) {
    if (wall[ii][jj][2] != 1 && wall[ii+1][jj+1][0] != 1) {
     tmp_map[ii + 1][jj + 1] += v;
     visited[ii + 1][jj + 1] = 1;
     q.push({ ii + 1, jj + 1, v - 1 });
    }
   }
  }
 }
}
void MakeWind() {
 memset(tmp_map, 0, sizeof(tmp_map));
 for (int i = 0; i < wind.size(); i++) {
  memset(visited, -1, sizeof(visited));
  if (wind[i].dir == 1) {
   tmp_map[wind[i].x][wind[i].y + 1] += 5;
   visited[wind[i].x][wind[i].y + 1] = 1;
   MoveR(wind[i].x, wind[i].y + 1, 4);
  }
  else if (wind[i].dir == 2) {
   tmp_map[wind[i].x][wind[i].y - 1]+= 5;
   visited[wind[i].x][wind[i].y - 1] = 1;
   MoveL(wind[i].x, wind[i].y - 1, 4);
  }
  else if (wind[i].dir == 3) {
   tmp_map[wind[i].x - 1][wind[i].y]+= 5;
   visited[wind[i].x - 1][wind[i].y] = 1;
   MoveU(wind[i].x - 1, wind[i].y, 4);
  }
  else if (wind[i].dir == 4) {
   tmp_map[wind[i].x + 1][wind[i].y] += 5;
   visited[wind[i].x + 1][wind[i].y] = 1;
   MoveD(wind[i].x + 1, wind[i].y, 4);
  }
 }
 for (int i = 1; i <= r; i++) {
  for (int j = 1; j <= c; j++) {
   map[i][j]+= tmp_map[i][j];
  }
 }
}
void ChangeTemp() {
 for (int i = 1; i <= r; i++) {
  for (int j = 1; j <= c; j++) {
   tmp_map[i][j] = map[i][j];
  }
 }
 
 for (int i = 1; i <= r; i++) {
  for (int j = 1; j <= c; j++) {
   if (j + 1 <= c) { //오른쪽
    if (wall[i][j][2] != 1) {
     int movei = i;
     int movej = j + 1;
      
     if (tmp_map[i][j]> tmp_map[movei][movej]) {
      int value = floor((tmp_map[i][j] - tmp_map[movei][movej]) / 4);
      map[i][j] -= value;
      map[movei][movej]+= value;
     }
     else if (tmp_map[i][j]< tmp_map[movei][movej]) {
      int value = floor((tmp_map[movei][movej] - tmp_map[i][j]) / 4);
      map[i][j]+= value;
      map[movei][movej] -= value;
     }
    }
   }
    
   if (i + 1 <= r) { //아래
    if (wall[i+1][j][0] != 1) {
     int movei = i + 1;
     int movej = j;
    
     if (tmp_map[i][j]> tmp_map[movei][movej]) {
      int value = floor((tmp_map[i][j] - tmp_map[movei][movej]) / 4);
      map[i][j] -= value;
      map[movei][movej]+= value;
     }
     else if (tmp_map[i][j]< tmp_map[movei][movej]) {
      int value = floor((tmp_map[movei][movej] - tmp_map[i][j]) / 4);
      map[i][j]+= value;
      map[movei][movej] -= value;
     }
    }
   }
  }
 }
}
void DecreaseTemp() {
 for (int j = 1; j <= c; j++) {
  if (map[1][j]> 0) {
   map[1][j] -= 1;
  }
  
  if (map[r][j]> 0) {
   map[r][j] -= 1;
  }
 }
 
 for (int i = 2; i < r; i++) {
  if (map[i][1]> 0) {
   map[i][1] -= 1;
  }
   
  if (map[i][c]> 0) {
   map[i][c] -= 1;
  }
 }
}
bool CheckTemp() {
 
 for (int i = 0; i < searchs.size(); i++) {
  if (map[searchs[i].first][searchs[i].second]< k) {
   return false;
  }
 }
 
 return true;
}
int main(void) {
 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) {
    if (map[i][j] == 5) {
     searchs.push_back({ i,j });
    }
    else {
     wind.push_back({ i,j,map[i][j] });
    }
   }
   map[i][j] = 0;
  }
 }
 memset(wall, -1, sizeof(wall));
 int w;
 cin >> w;
 for (int i = 0; i < w; i++) {
  int x, y, d;
  cin >> x >> y >> d;
  if (d == 0) { //세로 벽
   wall[x][y][0] = 1;
   wall[x - 1][y][1] = 1;
  }
  else if (d == 1) { //가로 벽
   wall[x][y][2] = 1;
   wall[x][y + 1][3] = 1;
  }
 }
 
 while (answer <= 100) {
  MakeWind();
  ChangeTemp();
  DecreaseTemp();
  answer++;
  if (CheckTemp()) break;
 }
 
 if (answer > 100)
  cout << 101 << endl;
 else
  cout << answer << endl;
}