백준27469 퀸 움직이기

작성일 | In

문제 링크

  • http://icpc.me/27469

사용 알고리즘

  • DP

시간복잡도

  • $O(KNM)$

풀이

$k$번 이동했고 마지막에 $d$방향으로 움직였을 때 $(i, j)$에 도달하는 경우의 수를 $D(k, d, i, j)$라고 정의합시다. 상태 공간 $8KNM$개, 상태 전이는 매번 약 $O(2(N+M))$개라서 너무 오래 걸립니다.
하지만 $D(k, d, i, j)$를 구하기 위해 필요한 이전 상태를 생각해 보면, 2차원 배열 $D(k-1, \ast)$에서 가로로 연속한 몇 개의 칸, 세로로 연속한 몇 개의 칸, 대각선으로 연속한 몇 개의 칸만 필요하다는 것을 알 수 있습니다. 따라서 4방향에 대해 누적 합 배열을 만들면 상태 전이의 개수를 7~8번 정도로 줄일 수 있습니다.
전체 시간 복잡도는 $O(KNM)$이고, 상수가 60 정도 붙습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 998244353;
constexpr int di[] = {0, 0, 1, -1, 1, -1, 1, -1};
constexpr int dj[] = {1, -1, 0, 0, -1, 1, 1, -1};
inline void AddP(int &a, int b){ a += b; if(a >= MOD) a -= MOD; }
inline int Add(int a, int b){ return (a += b) < MOD ? a : a - MOD; }
inline int Sub(int a, int b){ return (a -= b) >= 0 ? a : a + MOD; }

struct PrefixSum{
    int a[4][222][111], v[111][111];
    void clear(){ memset(a, 0, sizeof a); memset(v, 0, sizeof v); }
    void build(int n, int m){
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[0][i][j] = Add(a[0][i][j-1], v[i][j]);
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[1][i][j] = Add(a[1][i-1][j], v[i][j]);
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[2][i+j][i] = Add(a[2][i+j][i-1], v[i][j]);
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[3][i-j+111][i] = Add(a[3][i-j+111][i-1], v[i][j]);
    }
    void add(int r, int c, int x){ AddP(v[r][c], x); }
    int get(int r1, int c1, int r2, int c2) const {
        if(tie(r1,c1) > tie(r2,c2)) swap(r1, r2), swap(c1, c2);
        if(r1 == r2) return Sub(a[0][r1][c2], a[0][r1][c1-1]);
        if(c1 == c2) return Sub(a[1][r2][c1], a[1][r1-1][c1]);
        if(r1 + c1 == r2 + c2) return Sub(a[2][r1+c1][r2], a[2][r1+c1][r1-1]);
        if(r1 - c1 == r2 - c2) return Sub(a[3][r1-c1+111][r2], a[3][r1-c1+111][r1-1]);
        return 0;
    }
};

int N, M, K, A[111][111], si, sj, ei, ej;
pair<int,int> P[111][111][8];
PrefixSum D[2][8];
bool Check(int i, int j){ return 1 <= i && i <= N && 1 <= j && j <= M && A[i][j] == 0; }

void Get(int i, int j){
    if(A[i][j]) return;
    for(int k=0; k<8; k++){
        int r = i, c = j;
        while(Check(r+di[k], c+dj[k])) r += di[k], c += dj[k];
        P[i][j][k^1] = {r, c};
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) { char c; cin >> c; A[i][j] = c == '#'; }
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) Get(i, j);
    cin >> si >> sj >> ei >> ej;

    for(int k=0; k<8; k++){
        D[1][k].clear();
        int r = si + di[k], c = sj + dj[k];
        while(Check(r, c)) D[1][k].add(r, c, 1), r += di[k], c += dj[k];
    }

    for(int k=2; k<=K; k++){
        for(int d=0; d<8; d++) D[k-1&1][d].build(N, M);
        for(int d=0; d<8; d++) D[k&1][d].clear();
        for(int d=0; d<8; d++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=M; j++){
                    if(A[i][j]) continue;
                    for(int t=0; t<8; t++){
                        if(d == t || !Check(i-di[t], j-dj[t])) continue;
                        D[k&1][t].add(i, j, D[k-1&1][d].get(i-di[t], j-dj[t], P[i][j][t].first, P[i][j][t].second));
                    }
                }
            }
        }
    }
    int res = 0;
    for(int k=0; k<8; k++) AddP(res, D[K&1][k].v[ei][ej]);
    cout << res;
}