백준 34588 (C++) Explosive Slabstones Rearrangement

최초 업로드: 2025-10-30 02:22:38

최근 수정 시간: 2025-10-30 02:22:38

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] Explosive Slabstones Rearrangement

[문제 링크](https://www.acmicpc.net/problem/34588)

## 문제 설명

Barbara has a garden. The garden can be represented as a $n \times m$ grid. She has placed $k$ slabstones in the garden, so she can enjoy stepping slabstones from one to another every day. The slabstones are indexed from $1$ to $k$. Each slabstone fully occupies some cell of the garden, and no two slabstones are placed at the same cell.

However, an evil person, Babara, is going to place a special device that will occupy a rectangular region in the garden. If any slabstone overlaps with the device, it will explode and destroy the whole garden!

To avoid the explosion, Barbara wants to rearrange the slabstones by shifting the slabstones within the garden. The slabstones should remain non-overlapping during slabstone rearrangement. The energy spent is equal to the largest index among all slabstones that have been moved. Now Barbara wants to know the minimum energy required to rearrange the slabstones, so she can save her energy for “other purposes”.

For example, suppose the device will be placed at the blue rectangle. Then Barbara can rearrange the slabstones as follows. Please note that the slabstones do not overlap during the whole process, not only after the rearrangement. All slabstones that have been moved have index at most $4$, so the energy spent is $4$.

## 입력

The first line contains three integers $n$, $m$ and $k$.

Followed by $k$ lines, the $i$-th of which contains two integers $x_i$ and $y_i$, representing that the $i$-th slabstone is located at the $y_i$-th cell of the $x_i$-th row.

The last line contains four integers $u_1$, $v_1$, $u_2$ and $v_2$, representing that the top-left corner of the device is located at the $v_1$-th cell of the $u_1$-th row, and the bottom-right corner of the device is located at the $v_2$-th cell of the $u_2$-th row.

## 출력

Print the minimum energy required to rearrange the slabstones. If no slabstones need to be moved, the energy spent is $0$. If the explosion cannot be avoided, just output $-1$.

## 풀이
에너지를 파라매트릭 서치로 찾고, 파란 사각형부터 현재 에너지 이하인 공간을 플러드 필 하고, 움직일 수 있는 빈 칸의 수가 파란 사각형에 속한 slabstone 개수보다 큰지 확인하였습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int board[501][501];
bool visited[501][501];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m, k; cin >> n >> m >> k;
 for(int i=1;i<=k;i++) {
 int x, y; cin >> x >> y;
 board[x][y]=i;
 }
 int u1, v1, u2, v2; cin >> u1 >> v1 >> u2 >> v2;

int requireMove=0, left=0, right=n*m+1;
 for(int i=u1;i<=u2;i++) {
 for(int j=v1;j<=v2;j++) {
 if(board[i][j]) {
 requireMove++;
 left = max(left, board[i][j]);
 }
 }
 }

while(left<right) {
 int mid = left+right>>1;

int canMove=0;
 memset(visited, 0, sizeof visited);
 queue<pair<int, int>> q; q.push({u1, v1});
 visited[u1][v1]=true;
 while(!q.empty()) {
 auto [x, y] = q.front(); q.pop();
 for(int i=0;i<4;i++) {
 int nx = x+dx[i];
 int ny = y+dy[i];
 if(nx<=0 || nx>n || ny<=0 || ny>m || visited[nx][ny] || board[nx][ny]>mid) continue;
 if(!board[nx][ny] && (nx<u1 || nx>u2 || ny<v1 || ny>v2)) canMove++;
 visited[nx][ny]=true;
 q.push({nx, ny});
 }
 }
 if(canMove>=requireMove) right=mid;
 else left=mid+1;
 }
 cout << (left==n*m+1 ? -1 : left);
}
```