Submission #1520000
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define QUEUE_SIZE 2500 // 最大で50*50のフィールドが与えられる
#define SUCCESS 1 // 成功
#define FAILURE 0 // 失敗
typedef int data;
data queue_data[QUEUE_SIZE]; // キューのデータ
data queue_field_y[QUEUE_SIZE]; // キューに入れる場所のデータ(y軸)
data queue_field_x[QUEUE_SIZE]; // キューに入れる場所のデータ(x軸)
int queue_head=0; // データの先頭
int queue_num=0; // データの個数
int KANRI[51][51]; // 探索済みかどうかマーク
int enqueue(data enq_data,data enq_y,data enq_x){
if(queue_num < QUEUE_SIZE){
queue_data[queue_head + queue_num] = enq_data;
queue_field_y[queue_head + queue_num] = enq_y;
queue_field_x[queue_head + queue_num] = enq_x;
queue_num ++;
return SUCCESS;
} else {
return FAILURE;
}
}
int dequeue(data *deq_data,data *deq_y,data *deq_x){
if(queue_num > 0){
*deq_data = queue_data[queue_head];
*deq_y = queue_field_y[queue_head];
*deq_x = queue_field_x[queue_head];
queue_num --;
queue_head ++;
return SUCCESS;
} else {
return FAILURE;
}
}
int main(){
int r,c,sy,sx,gy,gx;
scanf("%d %d %d %d %d %d",&r,&c,&sy,&sx,&gy,&gx);
char field_char[51][51]; // フィールドそのもの
data field_data[51][51]; // そこに行くまでの手数を記録する
int i;
for(i=0;i<r;i++){
scanf("%s",&field_char[i]);
}
sy --; sx --; gy --; gx --; // 与えられた地点の座標と設定した配列のズレを修正
field_data[sy][sx] = 0;
KANRI[sy][sx] = 1;
int move_y[4]={1,0,-1,0};
int move_x[4]={0,1,0,-1};
for(i=0;i<4;i++){
if(field_char[sy+(move_y[i])][sx+(move_x[i])]=='.'){
field_data[sy+(move_y[i])][sx+(move_x[i])] = field_data[sy][sx] + 1;
KANRI[sy+(move_y[i])][sx+(move_x[i])] = 1;
enqueue(field_data[sy+(move_y[i])][sx+(move_x[i])],sy+(move_y[i]),sx+(move_x[i]));
}
}
int DD,YY,XX,ans;
while(1){
dequeue(&DD,&YY,&XX);
for(i=0;i<4;i++){
if(field_char[YY+(move_y[i])][XX+(move_x[i])]=='.' && KANRI[YY+(move_y[i])][XX+(move_x[i])] != 1){
field_data[YY+(move_y[i])][XX+(move_x[i])] = DD + 1;
KANRI[YY+(move_y[i])][XX+(move_x[i])] = 1;
enqueue(field_data[YY+(move_y[i])][XX+(move_x[i])],YY+(move_y[i]),XX+(move_x[i]));
}
}
if(KANRI[gy][gx] == 1){
ans = field_data[gy][gx];
break;
}
}
printf("%d\n",ans);
}
Submission Info
Submission Time
2017-08-19 19:59:51+0900
Task
C - 幅優先探索
User
r67pr
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2435 Byte
Status
AC
Exec Time
1 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:47:28: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[51]’ [-Wformat=]
scanf("%s",&field_char[i]);
^
./Main.cpp:42:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d %d %d",&r,&c,&sy,&sx,&gy,&gx);
^
./Main.cpp:47:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",&field_char[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All
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
Case Name
Status
Exec Time
Memory
subtask0_sample01.txt
AC
1 ms
256 KB
subtask0_sample02.txt
AC
1 ms
256 KB
subtask0_sample03.txt
AC
1 ms
256 KB
subtask1_01.txt
AC
1 ms
256 KB
subtask1_02.txt
AC
1 ms
256 KB
subtask1_03.txt
AC
1 ms
256 KB
subtask1_04.txt
AC
1 ms
256 KB
subtask1_05.txt
AC
1 ms
256 KB
subtask1_06.txt
AC
1 ms
256 KB
subtask1_07.txt
AC
1 ms
256 KB
subtask1_08.txt
AC
1 ms
256 KB
subtask1_09.txt
AC
1 ms
256 KB
subtask1_10.txt
AC
1 ms
256 KB
subtask1_11.txt
AC
1 ms
256 KB
subtask1_12.txt
AC
1 ms
256 KB
subtask1_13.txt
AC
1 ms
256 KB
subtask1_14.txt
AC
1 ms
256 KB
subtask1_15.txt
AC
1 ms
256 KB
subtask1_16.txt
AC
1 ms
256 KB
subtask1_17.txt
AC
1 ms
256 KB
subtask1_18.txt
AC
1 ms
256 KB
subtask1_19.txt
AC
1 ms
256 KB
subtask1_20.txt
AC
1 ms
256 KB
subtask1_21.txt
AC
1 ms
256 KB
subtask1_22.txt
AC
1 ms
256 KB