BOJ 15938 더위 피하기

더위 피하기
(http:/boj.kr/15938)

좌표가 -100,000이상 100,000 이하라서 좌표 모두 배열을 만들어줄 수는 없다.
하지만 더위를 버틸 수 있는 시간이 200밖에 안 된다. 즉, 출발지에서 거리가 200이 넘는 곳은 어차피 갈 수가 없다.

그러므로 출발지에서 거리가 200 이내인 곳만, 출발지에서 상대적인 위치로 생각하면 된다. 그리고 BFS로 경우의 수를 센다.

#include <bits/stdc++.h>
 
using namespace std;
 
const long long r = 1e9 + 7;
const int dy[4] = { -1, 1, 0, 0 }, dx[4] = { 0, 0, -1, 1 };
 
long long d[401][401][201];
bool chk[401][401], in[401][401][201];
vector<pair<int, int> > cand[201];
 
int main() {
    int sy, sx, t, hy, hx, n;
    long long ans = 0;
 
    scanf("%d %d %d %d %d %d", &sy, &sx, &t, &hy, &hx, &n);
 
    if (!(200 + hy - sy >= 0 && 200 + hy - sy <= 400 && 200 + hx - sx >= 0 && 200 + hx - sx <= 400)) {
        printf("0");
 
        return 0;
    }
 
    hy = 200 + hy - sy;
    hx = 200 + hx - sx;
 
    while (n--) {
        int u, v;
 
        scanf("%d %d", &u, &v);
 
        if (200 + u - sy >= 0 && 200 + u - sy <= 400 && 200 + v - sx >= 0 && 200 + v - sx <= 400)
            chk[200 + u - sy][200 + v - sx] = true;
    }
 
    sy = 200;
    sx = 200;
 
    d[sy][sx][0] = 1;
    cand[0].push_back({ sy, sx });
    in[sy][sx][0] = true;
    for (int i = 0;i < t;++i)
        in[hy][hx][i] = true;
    for (int i = 0;i < t;++i) 
        for (pair<int, int> k : cand[i]) 
            for (int j = 0;j < 4;++j) {
                pair<int, int> x = { k.first + dy[j], k.second + dx[j] };
 
                if (x.first < 0 || x.first > 400 || x.second < 0 || x.second > 400 || chk[x.first][x.second])
                    continue;
 
                d[x.first][x.second][i + 1] += d[k.first][k.second][i];
                d[x.first][x.second][i + 1] %= r;
                if (!in[x.first][x.second][i + 1]) {
                    in[x.first][x.second][i + 1] = true;
                    cand[i + 1].push_back({ x.first, x.second });
                }
            }
 
    for (int i = 0;i <= t;++i) {
        ans += d[hy][hx][i];
        ans %= r;
    }
 
    printf("%lld", ans);
 
    return 0;
}