acm1417.cpp

福建师范大学第三届程序设计比赛中的一道试题.用回溯法解决.

#include <iostream>
using namespace std;
int main(){
	int text;
	cin>>text;
	while(text--){
		char m[12][12];
		int tag[12][12];
		int i,j,a,b,x,y,x1,y1,sx,sy,xx,xy,flag;
		int minlen;
		int k[100]={0};
		//用增量数组(dx[1],dy[1])~(dy[8],dy[8])表示北，东，南，西，东北，东南，西南，西北8个移动方向。
		int dx[9]={0,0,2,1,2,0,-2,-1,-2};
		int dy[9]={0,1,2,0,-2,-1,-2,0,2};
		cin>>a>>b;
		for(i=a;i>=1;i--)
		{
			for(j=1;j<=b;j++){
				cin>>m[j][i];
				if(m[j][i]=='S') { sx=j; sy=i; }
				if(m[j][i]=='X') { xx=j; xy=i; }
				tag[j][i]=0;
			}
		}
		minlen=10000;//初始化为无穷大。
		flag=false;
		x=sx; y=sy; tag[x][y]=1;
		i=1; k[i]=0;
		while(i>=1)
		{  
			while(k[i]<8)
			{
				k[i]=k[i]+1;
				x1=x+dx[k[i]]; y1=y+dy[k[i]];
				if((x1>=1)&&(x1<=b)&&(y1>=1)&&(y1<=a)&&(tag[x1][y1]==0)&&m[x1][y1]!='W')
				{
					if((x1==xx)&&(y1==xy))
					{
						flag=true;
						if(i<minlen)  minlen=i;
					//	for(j=1;j<=i;j++) cout<<k[j]<<' '; //输出找到所有路径。
					//	cout<<endl;
					}
					else
						if(i<minlen-1)//否则剪枝。
						{
							x=x1; y=y1; tag[x][y]=1; i=i+1; k[i]=0;
						}
				}
			}//回溯	
			i=i-1;
			tag[x][y]=0;//撤消标记。 
			x=x-dx[k[i]]; 
			y=y-dy[k[i]];
		}
		if(flag) 
			cout<<minlen<<endl;			
		else
			cout<<"NO ANSWER"<<endl;
	}
	return 0;
}