1.没回溯
2.dfs的话要搜索完整，不要搜到一个就停了，这样搜到不到最短
3.旁边是墙的话不能直接把墙碰碎
4.最好不规定方向吧，因为总是可以往四个方向走的。最开始我为了剪枝规定了不能往来的方向走，结果发现这么剪枝是错的
5.行列弄反了
6.还有路过终点就算赢了
最后附个渣代码，好歹也过了至少思想是对滴
#include <iostream>
#include <cstring>
using namespace std;
int w,h,board[25][25],si,sj,cnt,ans;
bool DFS(int i,int j)
{
	if(cnt>10)return false;
	if(board[i][j]==3)
	{ 
		if(ans>cnt){ ans=cnt;return true;}
		else return false;
	}
	if(i<1 || i> h || j<1 || j>w )return false;
	bool is_find=false;
	for(int k=1;k<=4;++k)
	{
		int di=i,dj=j,bi=-1,bj=-1;
		switch (k)
		{
		default:
			break;
		case 1:
			while(di>0)
			{
				if( board[di][dj]==3)break;
				if(board[di][dj]==1){ board[di][dj]=0;bi=di,bj=dj;++di;break;}
				--di;
			}
			break;
		case 3:
			while(di<=h)
			{
				if( board[di][dj]==3)break;
				if(board[di][dj]==1){ board[di][dj]=0;bi=di,bj=dj;--di;break;}
				++di;
			}
			break;
		case 4:
			while(dj>0)
			{
				if( board[di][dj]==3)break;
				if(board[di][dj]==1){ board[di][dj]=0;bi=di,bj=dj;++dj;break;}
				--dj;
			}
			break;
		case 2:
			while(dj<=w)
			{
				if( board[di][dj]==3)break;
				if(board[di][dj]==1){ board[di][dj]=0;bi=di,bj=dj;--dj;break;}
				++dj;
			}
			break;
		}
		if(di==i && dj==j){ if(bi!=-1 && bj!=-1)board[bi][bj]=1;continue;}
		++cnt;
		if(DFS(di,dj))is_find=true;
		--cnt;
		if(bi!=-1 && bj!=-1)board[bi][bj]=1;
	}
	if(is_find)return true;
	else return false;
}
int main()
{
	while(cin>>w>>h && (w || h))
	{
		memset(board,0,sizeof(board));
		for(int i=1;i<=h;++i)
			for(int j=1;j<=w;++j)
			{
				cin>>board[i][j];
				if(board[i][j]==2)si=i,sj=j;
			}
		cnt=0,ans=15;
		if(DFS(si,sj))cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

• Re:总结一下下大家可能的错误吧 (1922) robinho364 2013-10-19 18:48:28