HDu 1728 bfs最小カーブ数

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1728
これまでこのような最少カーブ数の問題はしたことがなく、一般的に最少を求めるにはbfsを使ったほうがいいはずだ.しかし、以前はbfsは一般的に最小ステップ数を求めるために使われていたが、通り過ぎた点をマークして行かないことができた.今本題は最小のカーブ数を求めているので、歩いた点をマークすることはできません.の現在の点に必要な最小カーブ数を記録する配列が必要です.この点のカーブ数が以前の点のカーブ数よりも小さい場合、または等しい場合は、この値を更新します.解が見つかるまで全図を巡る.
学習:bfsに対して最適解の変形を探す.カーブ数を更新する方法を理解し、最小を保証します.
背景:1,WAはカーブ数を保存する配列に対して無限に初期化されていない.2、MLEは各点についてカーブ数の判定を行い、前に保存した値よりも小さいか、等与だけが入队しないと列が爆発します.3、ACの後に枝切りも行いましたが、キューの要素をポップアップするのを忘れました.結果死サイクル...次回注意キューのヘッダ要素を取り出してからポップアップし、忘れないようにしたほうがいいです.の
カーブ数を判定するときは必ず号に等しくします.これは他人の問題解だhttp://972169909-qq-com.iteye.com/blog/1244218  図を見れば分かります.
コード:

//hdu 1728
#include
#include
#include
#define INF 10000000;
using namespace std;
int d1[4] = {0,0,1,-1};
int d2[4] = {1,-1,0,0};
int turn1[101][101];
char map[101][101];
int n,m,k;
int ok;
int sx,sy,ex,ey;
struct state
{
	int x,y;
	int turn;
	int dir;
}cur,next1;
void bfs(state temp)
{
	temp.dir = -1;
	temp.turn = 0;
	turn1[temp.x][temp.y] = 0;
	queue q;
	q.push(temp);
	while(!q.empty())
	{
		cur = q.front();
		q.pop();  //                    ，      。。           。。         。。 
		if(cur.x == ex-1 && cur.y == ey-1)
		{
			if(cur.turn <= k)
			{
				ok = 1;
				printf("yes
");
				return ;
			}
		}
		if(cur.turn > k)
		{
			//q.pop();  //              
			continue;
		}
		for(int i = 0;i < 4;i++)
		{
			next1.x = cur.x + d1[i];
			next1.y = cur.y + d2[i];
			if(next1.x>=0&&next1.x=0&&next1.y