2（用一个2维数组）.txt

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

#include <iostream>
using namespace std;

int main(){
	int text;
	cin>>text;
	while(text--){
	    char m[10][10];
//		int tag[12][12];
		int i,j,a,b,x,y,x1,y1,sx,sy,xx,xy,flag;
		int minlen;
		int k[81];
		int dx[8]={0,2,1,2,0,-2,-1,-2};
		int dy[8]={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; m[x][y]='W';
		i=1; k[i]=-1;
		while(i>=1)
		{  
			while(k[i]<7)
			{
				k[i]=k[i]+1;
				x1=x+dx[k[i]]; y1=y+dy[k[i]];
				if((x1>=1)&&(x1<=b)&&(y1>=1)&&(y1<=a))
				{
					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(m[x1][y1]=='B'&&i<minlen)
						{
							x=x1; y=y1; m[x][y]='W'; i=i+1; k[i]=-1;
						}
				}
			}//回溯	
			i=i-1;
			m[x][y]='B'; 
			x=x-dx[k[i]]; 
			y=y-dy[k[i]];
		}
		if(flag) 
			cout<<minlen<<endl;			
		else
			cout<<"NO ANSWER"<<endl;
	}
	return 0;
}