C - 幅優先探索 / AtCoderBeginnerContest #007

abc007.contest.atcoder.jp

#include <iostream>
#include <string>
#include <queue>
using namespace std;

#define MAX 50

typedef pair<int,int> P_II;

int BFS(int r, int c, string field[], int start, int goal)	{
	int step=0;
	bool flg[MAX][MAX]={ {false} };
	const int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
	queue<P_II> que;

	que.push( P_II(0,start) );
	while ( !que.empty() )	{
		P_II p_ii=que.front(); que.pop();
		if ( !flg[p_ii.second/100][p_ii.second%100] )	{
			flg[p_ii.second/100][p_ii.second%100]=true;
			step=p_ii.first;
			if (p_ii.second == goal)	break;
			for (int i=0; i<4; ++i)	{
				int y=p_ii.second/100+dy[i], x=p_ii.second%100+dx[i];
				if (0<=y && y<r && 0<=x && x<c && field[y][x]=='.' && !flg[y][x])	que.push( P_II(step+1,y*100+x) );
			}
		}
	}
	return step;
}

void Solve(int r, int c)	{
	string field[MAX];
	int sy, sx, gy, gx;

	cin >> sy >> sx >> gy >> gx;
	for (int i=0; i<r; ++i)
		cin >> field[i];
	cout << BFS(r,c,field,(sy-1)*100+(sx-1),(gy-1)*100+(gx-1) ) << endl;
}

int main(void)	{
	int r, c;

	cin >> r >> c;
	Solve(r,c);
	return 0;
}

xとyの座標が50以下であることから、100を掛けて繋げた。
その後、目的地までの距離を数え出力。
～了～