Submission #2387613


Source Code Expand

//幅優先探索
//https://abc007.contest.atcoder.jp/tasks/abc007_3
#include<vector>
#include<iostream>
#include<string>
#include<queue>

#define MAX_N 100
#define MAX_M 100
using namespace std;
const int INF = 100000000;
string maze[MAX_N];
int N, M;
int sx, sy;//start
int gx, gy;//goal
int d[MAX_N][MAX_M];//各点までの最短距離の配列
					//移動4方向のベクトル
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//(sx,sy)から(gx,gy)の最短距離
//たどりつけないとINF
int bfs()
{
	queue<pair<int, int>>que;
	//全ての点をINFで初期化
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			d[i][j] = INF;
		}
	}
	//スタート地点をキューに入れ、その点の距離を0にする
	que.push(make_pair(sx, sy));
	d[sy][sx] = 0;

	//キューが空になるまでループ
	while (que.size())
	{
		//キューの先頭を取り出す
		pair<int, int> p = que.front();
		que.pop();
		//取り出してきた状態がゴールなら探索をやめる
		if (p.first == gx && p.second == gy)
		{
			break;
		}
		//移動4方向をループ
		for (int i = 0; i < 4; i++)
		{
			//移動した後の点を(nx,ny)とする
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			//移動が可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny]!=INFなら訪れたことがある)
			if ((0 <= ny && ny < N) && (0 <= nx && nx < M) && (maze[ny][nx] != '#') && (d[ny][nx] == INF))
			{
				//移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
				que.push(make_pair(nx, ny));
				d[ny][nx] = d[p.second][p.first] + 1;
			}
		}
	}
	return d[gy][gx];
}
int main()
{

	cin >> N >> M;

	cin >> sy >> sx; sx--; sy--;

	cin >> gy >> gx; gx--; gy--;
	for (int i = 0; i < N; i++)
	{
		cin >> maze[i];
	}
	int res = bfs();
	cout << res << endl;
	return 0;

}

Submission Info

Submission Time
Task C - 幅優先探索
User doikimihiro
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1961 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