[Baekjoon 31418] 스펀지 | Python

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

---

문제

 

정해진 스펀지 내에서 일정 시간이 흘렀을 때 바이러스들의 분포의 수를 구하는 문제이다. 바이러스들은 1초에 대각선, 상하좌우 중 한 방향으로 한 칸 이동하거나 움직이지 않을 수 있다.

 

---

풀이

 

바이러스가 어디에 있을 수 있냐를 구하는 문제이다. 바이러스는 좌우로는 최대 $ T $ 만큼 이동할 수 있고, 상하로도 최대 $ T $ 만큼 이동할 수 있다. 대각선도 마찬가지이니 바이러스 위치는 $ (2 \times T + 1) \times (2 \times T + 1) $ 개의 가능성을 가진다.

그런데 바이러스는 스펀지에서 벗어나진 못하므로 바이러스가 이동하다가 좌우측, 상하측으로 스펀지에 막힐 가능성을 생각해야 한다. 만약 바이러스가 이동할 수 있는 최대 좌측 좌표가 1 보다 작다면 스펀지 밖이기 때문에 수정해주어야 하고, 우측으로는 가로 길이 $ W $ 보다 길다면 수정해주어야 한다. 아래로도 1 보다 작다면, 위로도 $ H $ 보다 작다면 수정해주어야 한다.

좌측이랑 하방 좌표는 $ \max $ 을 이용하면 되겠고, 우측이랑 상방은 $ \min $ 을 사용하면 되겠다.

각 좌표에 있는 바이러스가 있을 수 있는 모든 자리의 수를 구했다면 모두 곱하면 된다. 998244353 으로 나누어 나머지를 구하라 했으니 주의해야 한다.

 

---

코드

 

width, height, virus_num, time = map(int, input().split())
ans = 1
for _ in range(virus_num):
    x, y = map(int, input().split())
    ans = ans * (min(width, x+time) - max(1, x-time) + 1) * (min(height, y+time) - max(1, y-time) + 1) % 998244353
print(ans)