AtCoder Beginner Contest 007

Submission #3981522

Source codeソースコード

//////////////////////////////////
// Created by 永徳泰明 on 2019-01-12.
// https://atcoder.jp/contests/abc007/tasks/abc007_3
//////////////////////////////////
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dump(x)  cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define fill(x, y) memset(x,y,sizeof(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 999999999;

typedef tuple<int, int, int> t3;
int R, C;

void readFromInputfile() {
#ifdef LOCAL
    static std::ifstream in("/Users/hoo/CLionProjects/for_atcoder/input");
    std::cin.rdbuf(in.rdbuf());
#endif
}

void bfs(priority_queue<t3, std::vector<t3>, greater<> > &queue, t3 t, int m[][51]) {
    queue.pop();
    int x = get<1>(t);
    int y = get<2>(t);
    if (x < 0 || x >= C || y < 0 || y >= R || m[y][x] >= 0) {
        return;
    }
    int cost = get<0>(t);
    m[y][x] = cost;
    rep(i, 4) {
        queue.push(make_tuple(cost + 1, x + dx[i], y + dy[i]));
    }
}

int main() {
    readFromInputfile();

    int sy, sx, gy, gx;
    cin >> R >> C;
    cin >> sy >> sx >> gy >> gx;
    int m[51][51] = {};
    fill(m, -1);
    rep(i, R) {
        rep(j, C) {
            char t;
            cin >> t;
            if (t == '#') {
                m[i][j] = INF;
            }
        }
    }
    priority_queue<t3, std::vector<t3>, greater<> > queue;
    queue.push(make_tuple(0, sx - 1, sy - 1));

    while (!queue.empty()) {
        bfs(queue, queue.top(), m);
    }

//    rep(i, R) {
//        rep(j, C) {
//            if (m[i][j] != INF) {
//                cout << m[i][j];
//            } else {
//                cout << '#';
//            }
//        }
//        cout << endl;
//    }

    cout << m[gy - 1][gx - 1] << endl;

    return 0;
}

Submission

Task問題 C - 幅優先探索
User nameユーザ名 hoo89
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1891 Byte
File nameファイル名
Exec time実行時間 2 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
All 100 / 100 subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 2 ms 256 KB
subtask1_01.txt AC 2 ms 256 KB
subtask1_02.txt AC 2 ms 256 KB
subtask1_03.txt AC 2 ms 256 KB
subtask1_04.txt AC 2 ms 256 KB
subtask1_05.txt AC 2 ms 256 KB
subtask1_06.txt AC 2 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 2 ms 256 KB
subtask1_10.txt AC 2 ms 256 KB
subtask1_11.txt AC 2 ms 256 KB
subtask1_12.txt AC 2 ms 256 KB
subtask1_13.txt AC 2 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 2 ms 256 KB
subtask1_16.txt AC 2 ms 256 KB
subtask1_17.txt AC 2 ms 256 KB
subtask1_18.txt AC 2 ms 256 KB
subtask1_19.txt AC 2 ms 256 KB
subtask1_20.txt AC 2 ms 256 KB
subtask1_21.txt AC 2 ms 256 KB
subtask1_22.txt AC 2 ms 256 KB