AtCoder Beginner Contest 007

Submission #1707346

Source codeソースコード

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Point {
    int x;
    int y;
    bool operator==(const Point& pos) { return x==pos.x && y==pos.y; }
    bool operator!=(const Point& pos) { return x!=pos.x || y!=pos.y; }
};
vector<vector<int>> map;
int height, width;
bool can_move_on(Point pos){ 
    return pos.x>=0    && pos.y>=0 
        && pos.x<width && pos.y<height 
        && map[pos.y][pos.x] == -1; 
}
void input(){
    char tmp;
    for(auto &y: map)
        for(auto &x: y){
            cin >> tmp;        
            x = tmp=='.' ? -1 : -100;
        }
}
int main() {
    cin >> height >> width;

    Point start, goal;
    cin >> start.y >> start.x;
    start.x -= 1; start.y -= 1;
    cin >> goal.y >> goal.x;
    goal.x -= 1; goal.y -= 1;

    map.resize(height);
    for(auto &x: map) x.resize(width);
    input();

    queue<Point> que;
    que.push(start);
    map[start.y][start.x] = 0;
    while(!que.empty()){
        Point now = que.front(); que.pop();
        int step = map[now.y][now.x];
        if(now == goal) { cout << step << endl; return 0; } // Goal
        vector<int> next_x = {-1, 0, 1, 0};
        vector<int> next_y = {0 ,-1, 0, 1};
        for(int i=0; i<4; i++) {
            Point next = {now.x+next_x[i], now.y+next_y[i]};
            if(can_move_on(next)){
                map[next.y][next.x] = step+1;
                que.push(next);
            }
        }
    }
    cout << -1 << endl;
}

Submission

Task問題 C - 幅優先探索
User nameユーザ名 eliza0x
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1528 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 1 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 1 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