横型探索についての質問です

[getready]

初投稿させていただきます。今プロコンのCHaser用のソースを書いているのですが。そのプログラムに横型探索を搭載するために本を読んで学習したあとに既存のサンプルソースを書き直していたのですが自分のプログラムのなにがあっていてなにが間違っていてそれをどうすればよいのか全く分かりません。どうすればよいのか教えてください。お願いします

コード:

#include<cstdio>
//queueクラスのinclude
#include<queue>
//定数INF1000の宣言
#define INF -1

//std名前空間の宣言
using namespace std;

//z座標とy座標をメンバに持つ構造体Pの宣言
struct P{
	int x,y;
};


//初期マップの宣言 0:何もないマス 1:黒く塗りつぶされているマス
int Map[5][5]={{0,1,0,0,0},
		          {0,0,0,1,0},
			  {1,1,1,1,0},
			  {0,0,0,0,0},
			  {0,0,0,1,0}};
			   

//4方向を表すために用いる配列(x用)
int dx[4]={0,1,0,-1};
//4方向を表すために用いる配列(y用)
int dy[4]={1,0,-1,0};
/*
	この2つの配列については実際に使用しているfor文のところを見て
	ax,ayの値がどのように変化しているかトレースをしてみてください。
*/


//make_P→Pを作る　関数
//2つの引数を使って構造体Pを宣言してそれぞれをメンバとし、完成したP型の構造体を返す
P make_P(int a,int b)
{
	P s;s.x=a;s.y=b;
	return s;
}

int main()
{
	//P型のqueueクラスqの宣言
	queue<P> q;
	//qに初期座標である(0,0)を入れておく
	//make_Pを使うことでP型の変数が返ってくるのでこのように要素を追加できる
	q.push(make_P(0,0));

	//各マスに対する歩数を格納する配列cntの宣言
	int cnt[5][5];
	//cntのすべての要素をINFで初期化する
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			cnt[i][j]=INF;
		}
	}

	//初期座標までの歩数を0で初期化する
	cnt[0][0]=0;
	//q.empty()→qが空の状態かどうかを返す 空だったら:真　空じゃなかったら:偽
	while(!q.empty()){
		//qのfrontのx情報とy情報を取り出して変数xx,yyに格納する
		int xx=q.front().x,yy=q.front().y;

		//qの先頭を削除する。
		q.pop();

		//dx,dyを回すために使用するfor文(これを使うと4方向への処理がfor文のみで済む)
		for(int i=0;i<4;i++){
			//axにxx+dx[i]の値,ayにyy+dy[i]の値を代入する
			int ax=xx+dx[i],ay=yy+dy[i];
			//ax,ayがマップの範囲内に収まっているか？
			if(ax>=0 && ax<5 && ay>=0 && ay<5){
				//歩数の配列にまだ初期値が入っている(未到達)かつ
				//初期マップ上では黒く塗りつぶされていないか
				if(cnt[ax][ay]==INF && Map[ax][ay]!=1){
					//歩数に今いるマス(xx,yy)のマスまでの歩数+1を代入する(一歩動くから)
					cnt[ax][ay]=cnt[xx][yy]+1;
					//qに一歩動いた先のマスの座標を格納する。
					q.push(make_P(ax,ay));
				}
			}
		}
	}

	//歩数を格納している配列からゴールの座標の値を出力する
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			if(cnt[i][j]>0)printf("%3d",cnt[i][j]);
			else printf("  #");
		}
		puts("");
	}
	return 0;
}

横型探索を組み込みたいプログラムです
　　　　↓

コード:

各種動作のメソッド↓
getReady()
walkUp()
walkDown()
walkLeft()
walkRight()
searchUp()
searchDown()
searchLeft()
searchRight()
lookUp()
lookDown()
lookLeft()
lookRight()
putUp()
putDown()
putLeft()
putRight()
*/

/*******自作関数*******/
//ここに自作関数を宣言
void map_getready(void);//mapping
void map_searchup(void);//mapping
void map_searchdown(void);//mapping
void map_searchright(void);//mapping
void map_searchleft(void);//mapping
void map_lookup(void);//mapping
void map_lookdown(void);//mapping
void map_lookright(void);//mapping
void map_lookleft(void);//mapping
void map_walkdown(void);//mappng
void map_walkup(void);//mapping
void map_walkright(void);//mapping
void map_walkleft(void);//mapping
void f_baba(void); //外周
void check(void);//mapping check
void original(void);//実戦

/*********グローバル変数*********/
int wh_map[70][70]; 
int x=70/2;
int y=70/2;
int mode=1; //現在のモード
int old_mode=1; //前のモード
/*******************************/

int main()
{
	int i=0;
	int j=0;
	
	//サーバーと接続する。もし失敗したらプログラムを終了
	if(Connect()==false)return 0;

	for (i=0;i<70;i++)  //二次元配列の初期化
	{
		for (j=0;j<70;j++)
		{
			wh_map[i][j]=5;
		}
	}
	
	while(1)
	{

		map_getready();

		


		check();

		f_baba(); //外周

	}


	//↓ｷﾆｽﾝﾅ
	// ソケットの解放
	closesocket(sct);
	// winsocketの解放
	WSACleanup();
	return 0;
}

void map_walkup(void)
{
	walkUp();
	y--;
}

void map_walkright(void)
{
	walkRight();
	x++;
}

void map_walkdown(void)
{
	walkDown();
	y++;
}

void map_walkleft(void)
{
	walkLeft();
	x--;
}

void map_getready(void)
{
	getReady();
	

	int gr=0;
	int gr2=0;
	int gr3=1;
	
	
		if (v[2]==1 || v[4]==1 || v[6]==1 || v[8]==1) //上下左右に敵がいたらput
		{
			mode=6;
		}

		else if (v[1]==1 || v[3]==1 || v[7]==1 || v[9]==1) //斜めに敵がいたらput
		{
			mode=8;
		}

		else if (v[2]==3 || v[4]==3 || v[6]==3 || v[8]==3) //上下左右にハートがあったら取る
		{
			old_mode=mode;
			mode=5;
		}

		else if (v[1]==3 || v[3]==3 || v[7]==3 || v[9]==3) //斜めにハートがあったら取る
		{
			old_mode=mode;
			mode=7;
		}
	
	/*
	wh_map[y-1][x-1]=v[1];
	wh_map[y-1][x]=v[2];
	wh_map[y-1][x+1]=v[3];
	wh_map[y][x-1]=v[4];
	wh_map[y][x]=v[5];
	wh_map[y][x+1]=v[6];
	wh_map[y+1][x-1]=v[7];
	wh_map[y+1][x]=v[8];
	wh_map[y+1][x+1]=v[9];
	*/


	for (gr=-1;gr<=1;gr++)
	{
		for (gr2=-1;gr2<=1;gr2++)
		{
			wh_map[y+gr][x+gr2]=v[gr3++];
		}
	}

	
		

}

void map_searchup(void)
{
	searchUp();

	int su=0;

	/*
	wh_map[y-1][x]=v[1];
	wh_map[y-2][x]=v[2];
	wh_map[y-3][x]=v[3];
	wh_map[y-4][x]=v[4];
	wh_map[y-5][x]=v[5];
	wh_map[y-6][x]=v[6];
	wh_map[y-7][x]=v[7];
	wh_map[y-8][x]=v[8];
	wh_map[y-9][x]=v[9];
	*/

	for (su=1;su>=9;su++)
	{
		wh_map[y-su][x]=v[su];
	}
		
}

void map_searchright(void)
{
	searchRight();

	int sr=0;

	/*
	wh_map[y][x+1]=v[1];
	wh_map[y][x+2]=v[2];
	wh_map[y][x+3]=v[3];
	wh_map[y][x+4]=v[4];
	wh_map[y][x+5]=v[5];
	wh_map[y][x+6]=v[6];
	wh_map[y][x+7]=v[7];
	wh_map[y][x+8]=v[8];
	wh_map[y][x+9]=v[9];
	*/

	for (sr=1;sr>=9;sr++)
	{
		wh_map[y][x+sr]=v[sr];
	}
}

void map_searchdown(void)
{
	searchDown();

	int sd=0;

	/*
	wh_map[y+1][x]=v[1];
	wh_map[y+2][x]=v[2];
	wh_map[y+3][x]=v[3];
	wh_map[y+4][x]=v[4];
	wh_map[y+5][x]=v[5];
	wh_map[y+6][x]=v[6];
	wh_map[y+7][x]=v[7];
	wh_map[y+8][x]=v[8];
	wh_map[y+9][x]=v[9];
	*/

	for (sd=1;sd>=9;y++)
	{
		wh_map[y+sd][x]=v[sd];
	}
}

void map_searchleft(void)
{
	searchLeft();

	int sl=0;

	/*
	wh_map[y][x-1]=v[1];
	wh_map[y][x-2]=v[2];
	wh_map[y][x-3]=v[3];
	wh_map[y][x-4]=v[4];
	wh_map[y][x-5]=v[5];
	wh_map[y][x-6]=v[6];
	wh_map[y][x-7]=v[7];
	wh_map[y][x-8]=v[8];
	wh_map[y][x-9]=v[9];
	*/

	for (sl=1;sl>=9;sl++)
	{
		wh_map[y][x-sl]=v[sl];
	}
}

void map_lookup(void)
{
	lookUp();

	int lu=0;
	int lu2=0;
	int lu3=1;

	/*
	wh_map[y-3][x-1]=v[1];
	wh_map[y-3][x]=v[2];
	wh_map[y-3][x+1]=v[3];
	wh_map[y-2][x-1]=v[4];
	wh_map[y-2][x]=v[5];
	wh_map[y-2][x+1]=v[6];
	wh_map[y-1][x-1]=v[7];
	wh_map[y-1][x]=v[8];
	wh_map[y-1][x+1]=v[9];
	*/

	for (lu=-3;lu<=-1;lu++)
	{
		for (lu2=-1;lu2<=1;lu2++)
		{
			wh_map[y+lu][x+lu2]=v[lu3++];
		}
	}

}

void map_lookright(void)
{
	lookRight();

	int lr=0;
	int lr2=0;
	int lr3=1;

	/*
	wh_map[y-1][x+1]=v[1];
	wh_map[y-1][x+2]=v[2];
	wh_map[y-1][x+3]=v[3];
	wh_map[y][x+1]=v[4];
	wh_map[y][x+2]=v[5];
	wh_map[y][x+3]=v[6];
	wh_map[y+1][x+1]=v[7];
	wh_map[y+1][+2]=v[8];
	wh_map[y+1][x+3]=v[9];
	*/

	for (lr=-1;lr<=1;lr++)
	{
		for (lr2=1;lr2<=3;lr2++)
		{
			wh_map[y+lr][x+lr2]=v[lr3++];
		}
	}

}

void map_lookdown(void)
{
	lookDown();

	int ld=0;
	int ld2=0;
	int ld3=1;

	/*
	wh_map[y+1][x-1]=v[1];
	wh_map[y+1][x]=v[2];
	wh_map[y+1][x+1]=v[3];
	wh_map[y+2][x-1]=v[4];
	wh_map[y+2][x]=v[5];
	wh_map[y+2][x+1]=v[6];
	wh_map[y+3][x-1]=v[7];
	wh_map[y+3][x]=v[8];
	wh_map[y+3][x+1]=v[9];
	*/

	for (ld=1;ld<=3;ld++)
	{
		for (ld2=-1;ld2<=1;ld2++)
		{
			wh_map[y+ld][x+ld2]=v[ld3++];
		}
	}

}

void map_lookleft(void)
{
	lookLeft();

	int ll=0;
	int ll2=0;
	int ll3=1;

	/*
	wh_map[y-1][x-3]=v[1];
	wh_map[y-1][x-2]=v[2];
	wh_map[y-1][x-1]=v[3];
	wh_map[y][x-3]=v[4];
	wh_map[y][x-2]=v[5];
	wh_map[y][x-1]=v[6];
	wh_map[y+1][x-3]=v[7];
	wh_map[y+1][x-2]=v[8];
	wh_map[y+1][x-1]=v[9];
	*/

	for (ll=-1;ll<=1;ll++)
	{
		for (ll2=-3;ll2<=-1;ll2++)
		{
			wh_map[y+ll][x+ll2]=v[ll3++];
		}
	}

}

void f_baba(void) //外周
{

	if (mode==1)
	{
		if (v[8]!=2)
		{
			map_walkdown();
		}

		else 
		{
			map_walkright();
			mode=2;
		}
	}

	else if (mode==2)
	{
		if (v[6]!=2)
		{
			map_walkright();	
		}

		else 
		{
			map_walkup();
			mode=3;
		}
	}

	else if (mode==3)
	{

		if (v[2]!=2)
		{
			map_walkup();
			
		}

		else 
		{
			map_walkleft();
			mode=4;
		}
	}

	else if (mode==4)
	{
		if (v[4]!=2)
		{
			map_walkleft();
		}

		else
		{
			map_walkdown();
			mode=1;
		}
	}

	else if (mode==5) //上下左右にハートがあったら取りに行く
	{
		if (v[2]==3)
		{
			map_walkup();
		}

		else if (v[4]==3)
		{
			map_walkleft();
		}

		else if (v[6]==3)
		{
			map_walkright();
		}

		else
		{
			map_walkdown();
		}

		mode=old_mode;
	}

	else if (mode==6) //上下左右に敵がいたらput　
		{
			if (v[2]==1)
			{
				putUp();
			}

			else if (v[4]==1)
			{
				putLeft();
			}

			else if (v[6]==1)
			{
				putRight();
			}

			else if (v[8]==1)
			{
				putDown();
			}
		}

	else if (mode==7) //斜めのハートを取りに行く
	{
		if (v[1]==3)
		{
			map_walkleft();
		}

		else if (v[3]==3)
		{
			map_walkright();
		}

		else if (v[7]==3)
		{
			map_walkleft();
		}

		else if (v[9]==3)
		{
			map_walkright();
		}

		mode=old_mode;

	}

	else if (mode==8) //斜めに敵がいたらput
	{
		if (v[1]==1)
		{
			map_walkleft();
		}

		else if (v[3]==1)
		{
			map_walkright();
		}

		else if (v[7]==1)
		{
			map_walkleft();
		}

		else if (v[9]==1)
		{
			map_walkright();
		}
		
		mode=old_mode;
	}


}

void check(void)  //mapping check
{
	int k=0;
	int l=0;
 
	printf ("現在の座標:");
	printf ("[%d]  [%d]\n",y,x);
	printf ("------------------------------------\n");
	
	for (k=0;k<70;k++)
	{
		for (l=0;l<70;l++)
		{
			if(x==l && y==k)
			{
				printf("O");//自分の現在位置
			}

			else if (wh_map[k][l]==0)
			{
				printf("!");//床
			}

			else if (wh_map[k][l]==3)
			{
				printf ("*");//ハート
			}

			else if (wh_map[k][l]==2)//ブロック
			{
				printf ("#");
			}

			else
			{
				printf ("%d",wh_map[k][l]); //初期化された二次元配列の値
			}
		}

		printf ("\n");
	}

	printf("\n----------------------------------------------------------------------");

蛇足ですが大会のサイトです
http://www.zenjouken.com/?page_id=517

[usao]

何がしたくて　現状どうなっていて　何がわからない状況にあるのか
全く読み取れないので回答のしようもありませんが，それ以前に
コンテスト用コードなのだとしたら
・全て自分でやらないとダメなような気がするけど，その点どうなんでしょう？
・こんなところでソース晒してたらまずくない？
…とか．

[getready]

文章が分かりにくかったようで申しわけありません。今回のせたソースは大会のサイトで公開されているサンプルソースを少し書き換えたものであり実践では到底戦えるものではないので載せても問題ありません。質問させていただいた横型探索が試合において必須らしくてコンテストの本を読み、既存のソースを書き換えていたのですが行き詰まったので質問させていただきました。

横型探索でブロックでふさがっている(通ることができない)経路以外で、アイテムまでの最短経路を求めたいです。

現状では、縦18マス　横27マスのマップを　要素数が70、70と多めにとった二次元配列 wh_map[70][70]で表現する。(自分が最初にいる座標が不定のため実際のマップより要素数を多めにとる必要がある)そして、その二次元配列を使って表現した架空のマップに実際のマップの情報を数値で格納(ブロックだったら2、アイテムだったら3)し、　int　Map[70][70]にwh_mapに格納されている情報をいれる(なにもなければ　0
ブロックがあれば　1)そして各マスに対する歩数を格納する配列cnt[70][70]を宣言し、それをすべて-1初期化する。そしてcnt[0][0]=0と
初期座標までの歩数を0で初期化して、queueを使用。←queueの中身をどうかえたらアイテムまでの最短経路を求められるのか悩んでいます。どうしたらうまくいくのでしょうか？

僕自身まだあまりC言語に触れていないのでどういうふうにしたら相手にわかりやすく伝わるのか分っていません。分りにくかったら本当に申し訳ありません。

[usao]

うーん，「コンテストだから１から１０まで自分でやらないとダメじゃない？」については置いといて（!?)も，
何が訊きたいのかいまいちよくわからないです．

(1)貼られているコードについて
コードが２つ貼られていますが，

・上側のは5*5の内容が全てわかっているとしたときのサンプル．
　横型探索処理を書いたつもり．
　（ただし，探索対象：ゴール　が何処なのかが不明）
・下側のはコンテストに関するコードだが探索処理は全く書かれていない

というものだという認識でＯＫでしょうか？

(2)やりたい内容について
ルールのPDFをざっとみた感じだと
・マップは未知だが，ターンを費やすことである範囲の情報を得ることができるみたいですが，
　今回の目的である探索処理にはこのプロセスも含まなければならないということですか？
　それとも，とりあえず上側のプログラムと同様に仮のマップ情報が埋まっている状態を考えて組みたいのでしょうか？
・あと，マップ上にはアイテムが複数存在するようですけど，経路探索の目的地（目指すアイテム）をどうやって決定する方針なのでしょうか？
　（一番最初に見つかったやつ＝一番近いやつ　とかいう単純な方法でしょうか？）
・経路を求めたいなら，queueにpushする情報に「これまでたどってきた経路」の情報も持たせればどうでしょうか

[getready]

極力自分の力でソースを書こうとは心がけていますが横型探索は長時間考えて資料も集めたのですがどうしても理解するまでに至らなかったのでお力添えしていただけるとありがたいです。

上のコードは5*5の範囲がすべて分っていると仮定したもので横型探索の処理を書いたつもりでした。下のコードはコンテスト用のコードですが
横型探索の処理はまったく書いていません。

やりたい内容ですがマップの情報が取得できている範囲で何か動作を起こすたびに横型探索を行います。
（取得できていない範囲は何もないと判断します）

目指すアイテムですが自分の座標から上下左右すべての方向に横型探索により歩数を割り振っていきアイテム(ゴール)に一番最初にたどりついた経路が最短かつ歩数が最小になりますので歩数が最小である経路をたどりアイテムを取りに行きたいのです。なのでまず歩数を割り振り
表示するつもりでプログラムを書いていたつもりだったのですがどこが間違っているのでしょうか？

こんな感じだと思います↓
(上の数値は座標を表し、下の数値が歩数を表している。なお、自分の座標は50　50と仮定する)


-------------
| 50 49 |
| 1 | 3
--------------------------------------------------------------------------------------------
48 50 | 49 50 | 50 50 | 51 50 | 52 50 |
2 | 1 | 0 | 1 | 2 |
--------------------------------------------------------------------------------------------------
| 50 49 | 51 50 |
| 1 | 2 |
--------------------------

[getready]

すみません表示がおかしくなってしまってますね

[getready]

すみません表示がおかしくなってしまってますね

[getready]

50 49 3
1
48 50 49 50 50 50 51 50 52 50
2 1 0 1 2

50 49 51 50
1 2

駄文失礼しました

[getready]

すみません、どうしても直りません

[たいちう]

> 極力自分の力でソースを書こうとは心がけていますが
> 横型探索は長時間考えて資料も集めたのですがどうしても
> 理解するまでに至らなかったのでお力添えしていただけるとありがたいです。

十分努力をしても成果が得られなかった場合ならば、不正を働いても良いのか、という話です。
募集要項等を見ても「掲示板で助言を求めないこと」などという項目は見つからなかったですし、
主催者も馬鹿ではないでしょうから、その程度の事は想定しているでしょう。

仮にばれなかったとして、この掲示板で得られたプログラムで(予選の？)上位に入れたら満足ですか？
(高校生とはいえ上位は天才達でしょうから、
プロだとしてもこのようなコンテストで上位に食い込める回答者は少ないでしょうが)

getreadyさんがまずすべきことは、十分応用ができるレベルまで、横型探索を学習することだと思いますが。
どんなに資料を集めても、理解できないなら仕方ないでしょ。
理解できないところを質問してみてはどうですか？

１．基本を十分理解する
２．やさしい問題に適用してみる
３．難しい問題に適用してみる

という順番で取り組むべきだと思うのですが、いきなり３．をやろうとしていませんか？

(横型探索が必須と思っているのも問題だけど、これは別の問題かも。
横型探索を使わないで、より優れたプログラムがあったら勝てませんよ。
この機会に横型探索を勉強することは無駄ではないでしょうから、やっぱり今は考えないで良いかな)

[getready]

横型探索は大会参加者が全員組み込んでいるので考えないというわけにはいかないんです。ですが自分でなんとか考えてみようとおもいます。ありがとうございました。

[usao]

頑張ってください．
探索処理自体の話がどうしても…という場合，例えば上側のコードだけで
Mapのどこかにゴールを設定（Map[0][0]=2; みたく適当に他と違う値をいれておくとか）して
そこまでの経路を探索したい　みたいな話にしてしまえば
コンテスト云々とは切り離して　純粋な探索処理に関する質問　にできると思います．
（実際の問題への適用はご自身でやればよい）

＃ＳＬＧの移動処理とか経路探索とかの話を検索すると参考になったりしませんかね？