# [Silver II] 자료 구조의 왕 [문제 링크](https://www.acmicpc.net/problem/31218) ## 문제 설명 <p>흐즈로는 어느 날 집 주변 잔디밭에 무성히 자란 잔디를 보고, 새로 산 잔디깎이 로봇의 성능을 시험해 보기로 했습니다. 잔디밭은 $n$개의 행과 $m$개의 열을 가진 2차원 격자로 구성되어 있으며, 그 중 $r$번째 행의 $c$번째 열에 해당하는 칸을 $(r,c)$로 표기합니다. 초기에 잔디밭의 모든 칸에는 잔디가 있습니다.</p> <p>잔디깎이 로봇에 네 정수 $d_y$, $d_x$, $y$, $x$를 입력하면, 초기에 $(y,x)$ 에서 출발하여 $\langle d_y,d_x \rangle$ 방향으로 이동하도록 설정됩니다. 이때 $|d_y|+|d_x|=1$이 항상 성립해야 합니다. 다시 말해, 잔디깎이 로봇은 항상 일정한 방향을 따라 이동하며, 상하좌우로 인접한 칸으로만 이동합니다. 잔디깎이 로봇은 다음과 같이 작동합니다.</p> <ol> <li>$(y,x)$에 잔디가 없다면 잔디 깎기를 종료합니다.</li> <li>$(y,x)$에 있는 잔디를 제거합니다.</li> <li>조건 $y+d_y<1$, $y+d_y>n$, $x+d_x<1$, $x+d_x>m$ 중 하나 이상이 참이라면 잔디 깎기를 종료합니다.</li> <li>$(y, x)$를 $(y+d_y, x+d_x)$로 변경한 뒤, 1번으로 돌아갑니다.</li> </ol> <p>흐즈로는 성능 시험의 일환으로 다음과 같은 쿼리 $Q$개에 대한 답을 찾아야 합니다.</p> <ul> <li>$1 \ d_y \ d_x \ y \ x$: 방향이 $\langle d_y,d_x \rangle$로 설정된 잔디깎이 로봇을 $(y,x)$에서 출발시킨 뒤, 해당 잔디깎이 로봇의 잔디 깎기가 끝날 때까지 대기합니다.</li> <li>$2 \ y \ x$: 쿼리가 들어오기 전 시작한 잔디 깎기가 <strong>순서대로</strong> 끝나고 난 뒤 $(y,x)$의 상태를 출력합니다. $(y,x)$에 잔디가 있다면 상태는 $0$, 잔디가 없다면 상태는 $1$입니다.</li> <li>$3$: 잔디밭에 잔디가 남아있는 칸의 개수를 출력합니다.</li> </ul> <p>모든 쿼리에 대해 정확한 답을 알지 못하면 잔디깎이 로봇이 제대로 작동하는지 확인할 수 없습니다. 주어진 $Q$개의 쿼리에 대해 정확히 대답하는 프로그램을 작성해 주세요.</p> ## 입력 <p>첫 번째 줄에 행의 개수 $n$, 열의 개수 $m$, 쿼리의 개수 $Q$가 공백으로 분리되어 주어집니다. ($1 \le n,m \le 1000$, $1 \le Q \le 2\times 10^5$)</p> <p>두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어집니다. 모든 쿼리는 본문에서 주어진 종류 중 하나입니다.</p> <p>모든 쿼리에 대해 $1 \le y \le n$, $1 \le x \le m$이며, 모든 $1$번 쿼리에 대해 $|d_y|+|d_x|=1$입니다.</p> ## 출력 <p>모든 $2$, $3$번 쿼리에 대해 정답을 한 줄에 하나씩 출력합니다.</p> ## 풀이 본문에 나온대로 시뮬레이션하면 됩니다. 모든 잔디가 깎이면 1번 쿼리로 깎이는 잔디가 없기에 1번쿼리의 시간복잡도의 합은 O(NM)입니다. 2번 쿼리는 그 자체로 O(1)입니다. 3번쿼리를 O(NM)에 구현하면 시간초과가 발생하기에 1번 쿼리를 진행하면서 남은 칸의 수를 업데이트를 하고 3번 쿼리는 출력만 해 O(1)에 해결 가능합니다. ``` c++ #include<bits/stdc++.h> using namespace std; bool board[1001][1001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; int remain=n*m; while(q--) { int z; cin >> z; if(z==1) { int dx, dy, x, y; cin >> dx >> dy >> x >> y; while(true) { if(x<1 || x>n || y<1 || y>m || board[x][y]) break; board[x][y]=true; x += dx; y += dy; remain--; } } else if(z==2) { int x, y; cin >> x >> y; cout << board[x][y] << '\n'; } else { cout << remain << '\n'; } } } ```