BOJ 31418 : 스펀지

• 문제 링크 : boj.kr/31418
• 난이도 : S4
• 태그 : 구현

31418번: 스펀지

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll W, H, K, T;
    cin >> W >> H >> K >> T;
    ll ans = 1;
    for(int i = 0; i < K; i++) {
        ll x, y;
        cin >> x >> y;
        ans *= (min(W, x + T) - max(1ll, x - T) + 1) % 998244353;
        ans %= 998244353;
        ans *= (min(H, y + T) - max(1ll, y - T) + 1) % 998244353;
        ans %= 998244353;
    }
    cout << ans;

    return 0;
}

---

풀이

바이러스의 가능한 분포는 변이 2T+1인 정사각형과 같다.

정사각형이 스펀지의 범위를 벗어나는 경우만 고려해서 구현해주면 된다.