Submission #1497707


Source Code Expand

#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <string>
#include <functional>
#include <cstdlib>
#include <queue>
#include <tuple>

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define DFOR(i,a) for(int i=(a);i>=0;i--)

using namespace std; 

int main(){
	queue<int> que; //meiro[que/R][que%R]=que,
	int R,C,sx,sy,gx,gy,i,j,target,tx,ty;
	char meiro[50][50];
	int  minmeiro[51][51];

	cin>>R>>C>>sy>>sx>>gy>>gx;
	FOR(i,0,R) cin>>meiro[i];

	FOR(i,1,R+1){
		FOR(j,1,C+1){
			if(meiro[i-1][j-1]=='#') minmeiro[i][j]=-100;
			else minmeiro[i][j]=-1;
		}
	}


	minmeiro[sy][sx]=0;
	que.push(sy*C+sx);
	
	while(1){
		target=que.front();
		if(que.empty()){
			puts("error!");
			exit(1);
		}else{
			que.pop();
		}
		ty=target/C;
		tx=target%C;
		if(tx==gx && ty==gy) break;

		if(minmeiro[ty][tx-1]==-1){
			minmeiro[ty][tx-1]=minmeiro[ty][tx]+1;
			que.push(ty*C+(tx-1));
		}
		if(minmeiro[ty][tx+1]==-1){
			minmeiro[ty][tx+1]=minmeiro[ty][tx]+1;
			que.push(ty*C+(tx+1));
		}
		if(minmeiro[ty+1][tx]==-1){
			minmeiro[ty+1][tx]=minmeiro[ty][tx]+1;
			que.push((ty+1)*C+tx);
		}
		if(minmeiro[ty-1][tx]==-1){
			minmeiro[ty-1][tx]=minmeiro[ty][tx]+1;
			que.push((ty-1)*C+tx);
		}
	}

	printf("%d\n",minmeiro[gy][gx]);

	return 0;
}

Submission Info

Submission Time
Task C - 幅優先探索
User stnae678
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1360 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
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