Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC代码:DFS(特别注意字典序输出)

Posted by xiexinxinlove at 2014-08-03 18:23:06 on Problem 2488
/*
 * POJ 2488
 * DFS进行遍历就好,记录走过的路径,只要不重复地走过p*q个方格就行了(结束条件) 
 */

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 30; 
int kase;
int p,q;
int vis[Max][Max]; //标记数组 
//方向数组,按照字典序就好了 
 int dir[8][2] = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//8个方向 
int path[Max*Max][2]; //用于记录DFS走过的路径
int flag; 

void dfs(int x, int y, int step)
{
	
	if(step == p*q) //走完了p*q格 
	{
		cout<<"Scenario #"<<++kase<<":"<<endl;
		for(int i=0; i<p*q; i++)
		{
			printf("%c%d",path[i][1]+'A',path[i][0]+1); //注意我们记录的路径下标都是从0开始的,按我这里的设计,先输出y值 
		}
		cout<<endl<<endl;
		flag = 1;
		return;
	}
		
	
	for(int d=0; d<8; d++)
	{
		int nx,ny; //只能做局部变量 
		nx = x + dir[d][0];
		ny = y + dir[d][1];
		if(!vis[nx][ny] && nx >= 0 && nx < p && ny >= 0 && ny < q) 
		{
			vis[nx][ny] = 1;
			path[step][0] = nx;
			path[step][1] = ny;
			dfs(nx, ny, step+1);
			vis[nx][ny] = 0; //取消标记
			if(flag)
				return; 
		}
	}
}

			
int main()
{
	int t;
	while(scanf("%d",&t) != EOF)
	{
		kase = 0;
		while(t--)
		{
			flag = 0;
			memset(vis, 0, sizeof(vis));
			scanf("%d %d",&p,&q);
			path[0][0] = 0;
			path[0][1] = 0;
			vis[0][0] = 1; 
			dfs(0,0,1);
			
			if(!flag)
			{
				cout<<"Scenario #"<<++kase<<":"<<endl;
				cout<<"impossible"<<endl<<endl;
			}
		}
	}
	return 0;
}
						 

/*
 这里注意几个问题:
 1、国际象棋,横着是字母,竖着是数字。
 2、是按字典序输出的,所以搜索方向上一定要注意!这里是个坑。 
 3、忽略“The knight can start and end on any square of the board.”这句话,这也
    算是个坑,实际上只要从A1点开始搜索就可以了,只要能从A1开始能搜到一条遍历全棋盘
	的路径,那么肯定从棋盘上的任意一个点作为起点都能搜出一条遍历棋盘的路径,并且题目
	要求要按字典序输出,所以只需从起点开始搜索就可以了!
*/						
						
						
						
						
					
					
					
					 
			 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator