AtCoder Beginner Contest 007

Submission #1678322

Source codeソースコード

#include <iostream>
#include <deque>
#include <vector>
#include <string>

int main(int argc, char const *argv[]) {

  int R, C;
  int sy, sx;
  int gy, gx;
  std::vector< std::vector<int> > field = *new std::vector<std::vector<int> >();

  std::cin >> R >> C;
  std::cin >> sy >> sx;
  std::cin >> gy >> gx;

  for(int r = 0; r < R; r++){
    std::vector<int> row = *new std::vector<int>();
    for(int c = 0; c < C; c++){
      char inp;
      std::cin >> inp;
      if(sy - 1 == r && sx - 1 == c){
        row.push_back(0);
      } else if(inp == '#'){
        row.push_back(-2);
      }else{
        row.push_back(-1);
      }
    }
    field.push_back(row);
  }

  std::deque<int> index_queue = *new std::deque<int>();
  index_queue.push_back((sy - 1) * C + (sx - 1));

  while(index_queue.size() > 0){
    int index = index_queue.front();
    index_queue.pop_front();

    int val = field[index / C][index % C];
    if(index / C == gy - 1 && index % C == gx - 1){
      std::cout << val << '\n';
      return 0;
    }

    if(index % C != 0){ //Not Most Left
      int left = index - 1;
      if(field[left / C][left % C] == -1){
        field[left / C][left % C] = val + 1;
        index_queue.push_back(left);
      }
    }

    if(index % C != C - 1){ //Not Most right
      int right = index + 1;
      if(field[right / C][right % C] == -1){
        field[right / C][right % C] = val + 1;
        index_queue.push_back(right);
      }
    }

    if(index >= C){ //Not Most Upper
      int upper = index - C;
      if(field[upper / C][upper % C] == -1){
        field[upper / C][upper % C] = val + 1;
        index_queue.push_back(upper);
      }
    }

    if(index < C * (R - 1)){ //Not Most lower
      int lower = index + C;
      if(field[lower / C][lower % C] == -1){
        field[lower / C][lower % C] = val + 1;
        index_queue.push_back(lower);
      }
    }
    //return 0;
  }

  return 0;
}

Submission

Task問題 C - 幅優先探索
User nameユーザ名 ysakuragi16
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 1997 Byte
File nameファイル名
Exec time実行時間 8 ms
Memory usageメモリ使用量 888 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 8 ms 888 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 2 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 2 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