poj 2488 DFS

最新推荐文章于 2019-07-13 17:07:34 发布

Yonggie

最新推荐文章于 2019-07-13 17:07:34 发布

阅读量162

点赞数

分类专栏：数据结构文章标签： dfs poj

本文链接：https://blog.csdn.net/Yonggie/article/details/84034976

版权

数据结构专栏收录该内容

59 篇文章

订阅专栏

其实就是典型的dfs了，不用剪枝，不用优化。

只不过要注意一点，就是字典序要最小。

字母小数组小的优先去搜。

AC代码：

#include <iostream> 
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn=30;

bool vis[maxn][maxn];
struct p{
	int x,y;
	p(int a,int b):x(a),y(b){}
	p(){}
}path[maxn];
int X,Y;
bool islegal(int x,int y){
	return x>0&&x<=X&&y>0&&y<=Y&&!vis[x][y];
}

bool CanI(int x,int y,int step){
	//cout<<"step = "<<step<<" "<<x<<y<<endl;
	path[step].x=x;path[step].y=y;
	if(step==X*Y) {
		for(int i=1;i<=step;i++)
			cout<<char(path[i].x-1+'A')<<path[i].y;
		cout<<endl;
		return 1;
	}
	else{
		vis[x][y]=1;
		
		
		if(islegal(x-2,y-1)){
			 if(CanI(x-2,y-1,step+1)) {return 1;}
			 else vis[x-2][y-1]=0;
		}
		if(islegal(x-2,y+1)){
			 if(CanI(x-2,y+1,step+1)) {return 1;}
			 else vis[x-2][y+1]=0;
		}
		
		
		if(islegal(x-1,y-2)){
			if(CanI(x-1,y-2,step+1)) {return 1;}
			else vis[x-1][y-2]=0;
		}
		if(islegal(x-1,y+2)){
			 if(CanI(x-1,y+2,step+1)) { return 1;}
			 else vis[x-1][y+2]=0;
		}
		
		
		if(islegal(x+1,y-2)){
			 if(CanI(x+1,y-2,step+1)) {return 1;}
			 else vis[x+1][y-2]=0;
		}
		if(islegal(x+1,y+2)){
			 if(CanI(x+1,y+2,step+1)) { return 1;}
			 else vis[x+1][y+2]=0;
		}
		
		
		if(islegal(x+2,y-1)){
			 if(CanI(x+2,y-1,step+1)) {return 1;}
			 else vis[x+2][y-1]=0;
		}
		if(islegal(x+2,y+1)){
			 if(CanI(x+2,y+1,step+1)) {return 1;}
			 else vis[x+2][y+1]=0;
		}
		return 0;	
	}
}
bool solve(){
	for(int i=1;i<=X;i++){
		for(int j=1;j<=Y;j++){
			if(CanI(i,j,1)){
				return 1;
			}
		}
	}
	cout<<"impossible"<<endl;
	return 0;
}
int main(){
	int n;
	cin>>n;
	int cas=1;
	while(n--) {
		
		cin>>Y>>X;
		memset(vis,0,sizeof(vis));
		memset(path,0,sizeof(path));
		cout<<"Scenario #"<<cas++<<":"<<endl;
		solve();
		cout<<endl;
		
	}
}

共勉。