結果

問題 No.340 雪の足跡
ユーザー masa
提出日時 2016-07-08 12:24:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 232 ms / 1,000 ms
コード長 2,595 bytes
コンパイル時間 971 ms
コンパイル使用メモリ 89,084 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-10-12 23:26:01
合計ジャッジ時間 6,580 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <queue>
#include <sstream>
#include <bitset>
using namespace std;
typedef pair<int, int> PII;
const int UP = 1;
const int DOWN = 1 << 1;
const int RIGHT = 1 << 2;
const int LEFT = 1 << 3;
string bin_str(int n) {
    stringstream ss;
    ss << static_cast<std::bitset<4> >(n);
    return ss.str();
}
void show(vector<int> &v) {
    for (auto e : v) {
        printf("%2d ", e);
    }
    printf("\n");
}
int main() {
    int w, h, n;
    scanf("%d %d %d", &w, &h, &n);
    vector<int> horizontal(w*h, 0);
    vector<int> vertical(w*h, 0);
    for (int i = 0; i < n; i++) {
        int m, b, b_prev;
        scanf("%d %d", &m, &b_prev);
        for (int j = 1; j <= m; j++) {
            scanf("%d", &b);
            int big = max(b, b_prev);
            int small = min(b, b_prev);
            if (big - small < w) {
                horizontal[small] += 1;
                horizontal[big] -= 1;
            } else {
                vertical[small] += 1;
                vertical[big] -= 1;
            }
            b_prev = b;
        }
    }
    // show(horizontal);
    // show(vertical);
    vector<int> connect(w * h, 0);
    for (int i = 0; i < h; i++) {
        int l = i * w;
        int r = (i + 1) * w - 1;
        // printf("lr %d %d\n", r, l);
        int ok_right = 0;
        for (int j = l; j <= r; j++) {
            ok_right += horizontal[j];
            if (ok_right > 0) {
                connect[j] |= RIGHT;
            }
        }
        int ok_left = 0;
        for (int j = r; j >= l; j--) {
            ok_left += horizontal[j];
            if (ok_left < 0) {
                connect[j] |= LEFT;
            }
        }
    }
    for (int i = 0; i < w; i++) {
        int d = i;
        int u = (h - 1) * w + i;
        int ok_up = 0;
        for (int j = d; j <= u; j += w) {
            ok_up += vertical[j];
            if (ok_up > 0) {
                connect[j] |= UP;
            }
        }
        int ok_down = 0;
        for (int j = u; j >= d; j -= w) {
            ok_down += vertical[j];
            if (ok_down < 0) {
                connect[j] |= DOWN;
            }
        }
    }
    // for (int i = 0; i < w * h; i++) {
    //  printf("connect %d %s\n", i, bin_str(connect[i]).c_str());
    // }
    vector<int> memo(w * h, -1);
    queue<int> que;
    int goal = w * h - 1;
    memo[0] = 0;
    que.push(0);
    int masks[4]   = {UP, DOWN, RIGHT, LEFT};
    int to_next[4] = {w,  -w,   1,     -1};
    while (!que.empty()) {
        auto now = que.front();
        que.pop();
// printf("now %d\n", now);
        if (now == goal) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            if (connect[now] & masks[i]) {
                auto next = now + to_next[i];
// printf("next %d %d\n", next, memo[next]);
                if (memo[next] == -1) {
                    memo[next] = memo[now] + 1;
                    que.push(next);
                }
            }
        }
    }
    if (memo[goal] == -1) {
        cout << "Odekakedekinai.." << endl;
    } else {
        cout << memo[goal] << endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0