やっと解けた

　人材獲得作戦・４　試験問題ほか
　
　一番最初にやったことがVisual C++ Expressをインストールしたことでした。

　思ったこと。

• 時々コード書く真似事はやってたけど、本格的に勉強しないとこういうところで差が出るんだね…
• というか一年ぶりくらいにC言語的なものに触れた気がする…
• こういうのって、日々やってないと全然わかんなくなるね。久々に頭を使った
  • こんなの頭を使ったうちに入らないって？
• 一応答え出てるけど、すごく冗長な気がする
  • 先にどのマスの隣にどのマスがあるか探索してるのが無駄すぎる気がする…
• 方針が決まるまで結構時間かかった
  • それを記述するのにも結構時間かかった。3時間は超えてるんじゃないかな
• 頭の中で動かすより、とりあえず書いてみて形を整えていく方が今の自分のレベルには合ってるっぽいなぁ
• でも頭の体操になるので、こういうの積極的にやってみた方が良さそうだ

#include <vector>
#include <iostream>

struct Point{
	int x, y;
};

using namespace std;

struct NodeData{
	int cost;
	vector<Point> next_node;
	Point pos;
	Point prv_pos;
};


NodeData *node;

//マップ

char map[] = 
"**************************"
"*S* *                    *"
"* * *  *  *************  *"
"* *   *    ************  *"
"*    *                   *"
"************** ***********"
"*                        *"
"** ***********************"
"*      *              G  *"
"*  *      *********** *  *"
"*    *        ******* *  *"
"*       *                *"
"**************************";

int width = 26;
int height = 13;

Point start,goal;

#define MAX 100000

bool WallCheck(int x, int y){
	if( map[ x + y * width] ==  '*')
		return true;
	return false;
}

void CreateNode(){
	for(int y = 0; y < height; y++){
		for(int x = 0; x < width; x++){
	
			node[ x + y * width].pos.x = x;
			node[ x + y * width].pos.y = y;

			node[ x + y * width].prv_pos.x = -1;
			node[ x + y * width].prv_pos.y = -1;

			node[ x + y * width].cost = MAX;

			Point pos;
			//壁以外のとき上下左右が壁かどうかを見る
			if( map[x + y * width]  != '*'){
				if(!WallCheck(x , y - 1)){
					pos.x = x; pos.y = y-1;
					node [ x + y * width].next_node.push_back(pos);
				}

				if(!WallCheck(x , y + 1)){
					pos.x = x; pos.y = y+1;
					node [ x + y * width].next_node.push_back(pos);
				}

				if(!WallCheck(x - 1, y)){
					pos.x = x - 1; pos.y = y;
					node [ x + y * width].next_node.push_back(pos);
				}

				if(!WallCheck(x + 1, y)){
					pos.x = x + 1; pos.y = y;
					node [ x + y * width].next_node.push_back(pos);
				}

			}

			if( map[x + y * width]  == 'S'){
				node [ x + y * width].cost = 0;
				start.x = x;
				start.y = y;
			}

			if( map[x + y * width]  == 'G'){
				goal.x = x;
				goal.y = y;
			}

				
				
			
		}
	}


}


int main(int argc,char** argv){
	//マップ読み込み
	node = new NodeData[width * height];
	//マップからノードデータ作成
	CreateNode();
	
	//探索開始ー
	vector<Point> search_node;
	vector<Point> next_search;
	next_search.push_back(start);
	
	bool reach_goal = false;

	int count = 0;
	while(!reach_goal){
		count++;
		search_node.clear();
		for(int i = 0; i < next_search.size(); i++)
			search_node.push_back(next_search[i]);
		next_search.clear();
		for(int i=0;i < search_node.size() && !reach_goal; i++){
			
			NodeData &now_node = node[ search_node[i].x + search_node[i].y * width];
			for( int j=0; j < now_node.next_node.size(); j++){
				//もしゴールだったらそこで終了
				if( now_node.next_node[j].x  == goal.x &&  now_node.next_node[j].y  == goal.y){
					node[goal.x + goal.y * width].prv_pos = search_node[i];
					reach_goal = true;
					break;
				}
				if( node[now_node.next_node[j].x + now_node.next_node[j].y * width].cost > count){
					node[now_node.next_node[j].x + now_node.next_node[j].y * width].cost = count;
					node[now_node.next_node[j].x + now_node.next_node[j].y * width].prv_pos  = search_node[i];
				//	node[now_node.next_node[j].x + now_node.next_node[j].y * width].prv_pos.y  =search_node[i].y;
					next_search.push_back(now_node.next_node[j]);
				}
			}
			
		}

		

		

	
		
	}
	cout << "ゴールまで" << count << "歩" << endl;

	cout << "入力したマップ" << endl;

	for(int y = 0; y <height; y++){
		for(int x = 0; x < width; x++){
			cout << map[x + y * width] ;
		}
		cout << endl;
	}

	cout << "最短経路" << endl;

	//ゴールまで出力
	Point prv_pos = node[goal.x + goal.y * width].prv_pos;
	for(int i = count-1 ; i != 0; i--){
		map[ prv_pos.x + prv_pos.y * width] = '$';
		prv_pos = node[ prv_pos.x + prv_pos.y * width].prv_pos;
	}
	
	for(int y = 0; y <height; y++){
		for(int x = 0; x < width; x++){
			cout << map[x + y * width] ;
		}
		cout << endl;
	}
		
	delete [] node;
	return 0;

}

入力したマップ
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
最短経路
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************