#26189 (C++11（廃止可能性あり）) No.124 門松列(3)

• 問題: No.124 門松列(3)
• ユーザー: masa
• 提出日時: 2015-05-11 23:03:39
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 5 ms / 5,000 ms
• コード長: 2,025 bytes
• コンパイル時間: 871 ms
• コンパイル使用メモリ: 88,816 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-05 23:16:37
• 合計ジャッジ時間: 1,933 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 26

ソースコード

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <tuple>
#include <set>
using namespace std;
const int XY_SHIFT = 1000;
typedef tuple<int, int, int> TPL_III;
bool isKadomatsuSequence(int val) {
    int a = val / 100;
    int b = val / 10 % 10;
    int c = val % 10;
// printf("abc %d %d %d (%d)\n", a, b, c, val);
    if (b == 0) {
        return true;
    }
    if (a == 0) {
        return (b != c);
    }
    if (a == b || b == c || c == a) {
        return false;
    }
    if (b == max({a, b, c}) || b == min({a, b, c})) {
        return true;
    }
    return false;
}
int main() {
    int w, h;
    cin >> w >> h;
    vector< vector<int> > board(h, vector<int>(w, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> board[i][j];
        }
    }
// cout << endl << endl;
    int dx[4] = {1, 0 , -1, 0};
    int dy[4] = {0, 1, 0, -1,};
    TPL_III tpl;
    vector< vector< set<int> > > came(h, vector<set<int> >(w, set<int>()));
    queue<TPL_III> que;
    int x, y, kdmt;
    int nx, ny, nkdmt, nstep;
    x = 0;
    y = 0;
    kdmt = board[y][x];
    que.push(make_tuple(y * XY_SHIFT + x, kdmt, 0));
    for (int i = 0; i < 1000; i++) {
        came[y][x].insert(i);
    }
    while(!que.empty()) {
        tpl = que.front();
        que.pop();
        x = get<0>(tpl) % XY_SHIFT;
        y = get<0>(tpl) / XY_SHIFT;
        kdmt = get<1>(tpl) * 10 % 1000;
        nstep = get<2>(tpl) + 1;
// printf("xy %d %d %d %d\n", x, y, get<1>(tpl), get<2>(tpl));
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
                continue;
            }
            nkdmt = kdmt + board[ny][nx];
// printf("nxy %d %d %d\n", nx, ny, nkdmt);
            if (came[ny][nx].count(nkdmt) > 0) {
                continue;
            }
            if (isKadomatsuSequence(nkdmt)) {
                if (nx == w - 1 && ny == h - 1) {
                    cout << nstep << endl;
                    return 0;
                }
// printf("first came %d %d %d\n", ny, nx, nkdmt);
                came[ny][nx].insert(nkdmt);
                que.push(make_tuple(ny * XY_SHIFT + nx, nkdmt, nstep));
            }
        }
    }
    cout << -1 << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX