오랜만에 구현 문제를 푸니까 엄청 귀찮고 잔실수도 많았다...
모든 에어컨을 큐에 넣고 조건에 맞도록 bfs를 돌리면 된다.
구현은 언제 물 흐르듯 할 수 있을가...
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int arr[2002][2002];
int n, m, ans = 0;
vector<pii> acs;
bool visited[2002][2002][4];
struct state {
int x, y, d;
state(int xx, int yy, int dd) {
x = xx, y = yy, d = dd;
}
};
void input() {
cin >> n >> m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> arr[i][j];
if(arr[i][j] == 9) acs.push_back({i, j});
}
}
}
int main() {
fastio;
input();
queue<state> q;
for(auto it = acs.begin(); it != acs.end(); ++it) {
pii ac = *it;
for(int i = 0; i < 4; ++i) {
visited[ac.first][ac.second][i] = true;
q.push(state(ac.first, ac.second, i));
}
}
while(!q.empty()) {
auto [fx, fy, fd] = q.front(); q.pop();
// move
int nx = fx + dx[fd], ny = fy + dy[fd];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny][fd]) continue;
visited[nx][ny][fd] = true;
// x directional change
if(!arr[nx][ny]) q.push(state(nx, ny, fd));
else if(arr[nx][ny] == 1) {
if(fd & 1) q.push(state(nx, ny, 4 - fd));
else q.push(state(nx, ny, fd));
}
else if(arr[nx][ny] == 2) {
if(fd & 1) q.push(state(nx, ny, fd));
else q.push(state(nx, ny, 2 - fd));
}
else if(arr[nx][ny] == 3) q.push(state(nx, ny, 3 - fd));
else {
if(fd < 2) q.push(state(nx, ny, 1 - fd));
else q.push(state(nx, ny, 5 - fd));
}
}
for(int i = 0 ; i < n; ++i) {
for(int j = 0; j < m; ++j) {
for(int k = 0; k < 4; ++k) {
if(visited[i][j][k]) {
ans++;
break;
}
}
}
}
cout << ans;
return 0;
}
백준 21924 도시 건설 혼내주기 (0) | 2022.03.03 |
---|---|
백준 21923 곡예 비행 혼내주기 (0) | 2022.03.03 |
백준 21921 블로그 혼내주기 (0) | 2022.02.28 |
백준 14466 소가 길을 건너간 이유 6 혼내주기 (0) | 2021.10.13 |
백준 1937 욕심쟁이 판다 혼내주기 (0) | 2021.09.27 |
댓글 영역