人材獲得作戦・４ 試験問題やってみた

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

Twitterで流れてたのでアニメ視聴を中止して参加。
だいたい40分ぐらいで書けました。
42人受験者がいて、2人しかLv4の解答をしていないことに心底驚きました。
この道に進んだ人が50人いたら、20人ぐらいはLv4まで解答するだろう、ぐらいにこの業界を考えてましたけど
そうでもないのか？…うーん。

条件に記述されている、
・入力データのバリデーション（長方形になっているか、スタート・ゴールが１つずつあるかどうか、等）は不要


という条件の意味がよくわからないので
とりあえず、マップがx軸が可変長の場合も考慮したコードを書いた。
中途半端すぎるｗ


以下コードと解法。
幅優先探索(BFS)で最短経路を探索した後、再帰で経路を$で埋めた。

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};
vector<string> V;
vector<vector<int> > memo;

void fill(int x,int y)
{
	int SMIN = 10000000;
	int selectK = -1;
	for(int k=0;k<4;k++){
		int tx = dx[k]+x;
		int ty = dy[k]+y;
		if(tx<0 || ty<0 || ty>=memo.size() || tx>=memo[ty].size()
			|| V[ty][tx]=='*')continue;
		if(SMIN > memo[ty][tx]){
			SMIN = memo[ty][tx];
			selectK = k;
		}
	}
	if(V[y+dy[selectK]][x+dx[selectK]]=='S'){
		return ;
	}
	V[y+dy[selectK]][x+dx[selectK]]='$';
	fill(x+dx[selectK],y+dy[selectK]);
	return ;
}

int main()
{
	string str;
	int startX,startY,goalX,goalY;
	for(int i=0;getline(cin,str);i++){
		V.push_back(str);
		memo.push_back(vector<int>(str.size(),10000000));
		if(str.find("S",0)!=-1){
			startX = str.find("S",0);
			startY = i;
		}
		if(str.find("G",0)!=-1){
			goalX = str.find("G",0);
			goalY = i;
		}
	}
	queue<pair<int,int> > q;
	q.push(make_pair(startX,startY));
	memo[startY][startX] = 0;
	
	int alreadyGoal = 0;
	for(;!q.empty();){
		queue<pair<int,int> > qtmp;
		for(;!q.empty()&&!alreadyGoal;){
			pair<int,int> p = q.front();
			q.pop();
			for(int k=0;k<4;k++){
				int tx = dx[k]+p.first;
				int ty = dy[k]+p.second;
				if(tx<0 || ty<0 || ty>=memo.size() || tx>=memo[ty].size()
					|| memo[p.second][p.first]+1 >= memo[ty][tx]
					|| V[ty][tx]=='*')continue;

				memo[ty][tx] = memo[p.second][p.first]+1;
				
				if(V[ty][tx]=='G'){
					alreadyGoal = 1; break;
				}
				qtmp.push(make_pair(tx,ty));
			}
		}
		if(alreadyGoal)break;
		q = qtmp;
	}
	fill(goalX,goalY);
	for(int i=0;i<V.size();i++){
		cout<<V[i]<<endl;
	}
	return 0;
}

A*っていう探索アルゴリズムがあるらしいことを知った。
今度勉強しよう。