読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

ABC007-C 幅優先探索|AtCoder

AtCoder コード 幅優先探索(BFS) 競プロ

C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder を解きました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef pair<int, int> PII;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = numeric_limits<int>::max();
int main()
{
	int row{}, col{};//行,列
	int sy{},sx{};//スタート地点の座標(y,x)
	int gy{},gx{};//ゴール地点の座標(y,x)
	cin >> row >> col >> sy >> sx >> gy >> gx;

	char C[row+1][col+1];
	REP( i, row )
	{
		REP( j, col )
		{
			cin >> C[i+1][j+1];//座標は1,1から始まるので+1して合わせる
		}
	}

	int distance[row+1][col+1];//距離格納配列
	fill(distance[0], distance[row], INF);//配列初期化

	queue<PII> q;
	q.emplace( sy, sx );//スタート地点座標をqueueに代入
	distance[sy][sx] = 0;//初期状態からの距離を0に設定

	int dy[4] = { 1, 0, -1, 0 }, dx[4] = { 0, 1, 0, -1 };//移動4方向のベクトル

	while( !q.empty() )
	{
		PII now = q.front();//現在地
		q.pop();

		//移動4方向をループ
		REP( i, 4 )
		{
			//移動した後の点を(ny,nx)とする
			int ny = now.first + dy[i], nx = now.second + dx[i];

			//移動が可能かの判断と既に訪れた事があるかの判定
			if( 0 <= ny && ny <= row && 0 <= nx && nx <= col && C[ny][nx] != '#' && distance[ny][nx] == INF )
			{
				q.emplace( ny, nx );//次の位置をqueueに入れる
				distance[ny][nx] = distance[now.first][now.second] + 1;//点の距離をnowから+1の距離で確定する                
			}   
		}
	}
	cout << distance[gy][gx] << endl;
	return 0;
}

問題のタイトル通り幅優先探索(BFS)で解ける問題です。
迷路の座標が 1, 1 から始まるのに対して、配列は 0, 0 からなのに気付かず...
OUTPUTが全然一致しなくて時間が掛かりました...。

他に失敗していた点としては、二次元配列をINFで埋める所ですかね。
色々な方法がありますが、私は std::fill で埋めました。

凄く久し振りにABC-Cを埋めれました...!
(アルゴリズムを知らないので解ける問題がもう無かった)

参考
fill - cpprefjp C++日本語リファレンス
C++で多次元配列を一行で初期化 - Qiita