`
jackchen0227
  • 浏览: 147329 次
  • 性别: Icon_minigender_1
  • 来自: 帝都
社区版块
存档分类
最新评论

骑士问题--特殊的bfs

    博客分类:
  • ACM
阅读更多



 这个是来自 国际大学生程序设计竞赛例题解(1)的题目

很简单的一道搜索题目,但是没有使用dfs,

使用的是特殊的bfs,非常巧妙

代码

/*
Qi Shi Wen Ti
 similar to eight queens
 use bfs() to get the min step
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int queue[1000][2];

int matrix[8][8];
int startX,startY,endX,endY;
int head = -1,tail = 0;
int dir[8][2] = {{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
void put(int x,int y)
{
	tail ++;
	if(tail >= 1000)
		tail = tail % 1000;
	queue[tail][0] = x;
	queue[tail][1] = y;
}
void get(int * x,int * y)
{
	head ++;
	if(tail < head)
	{
		printf("queue error!\n");
		exit(0);
	}	
	*x = queue[head][0];
	*y = queue[head][1];		
}
int queueEmpty()
{
	return tail < head ? 1:0; 
}
/* 
	the problem is how to calculate the step
	it seems like it's hard to find out one step's next step in the bfs search
	while it is easy in the dfs search;

    standard bfs
*/
void bfs(int startX,int startY,int endX,int endY)
{
	int curX,curY;
	int minStep=0,step=0;;
	put(startX,startY);
	while(! queueEmpty())
	{
		get(&curX,&curY);
		matrix[curX][curY] = 1;
		if(curX == endX && curY == endY)
		{
			if(step > minStep)
				minStep = step;
		}
		else if( 1) 
		{
			
		}
		else
		{
			for(int j=0;j<8;j++)
			{
				curX += dir[j][0];
				curY += dir[j][1];
				if(matrix[curX][curY] != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8)
					put(curX,curY);
			}
		}
	}
}
/*
	special Bfs 
	it visited all nodes in a layer (just a layer's node int bfs tree) in a round
*/

int specialBfs(int startX,int startY,int endX,int endY)
{
	int head =0,tail =1,tmpTail;
	int step = 0;
	int curX = startX,curY = startY;

	queue[head][0] = startX;
	queue[head][1] = startY;
	matrix[curX][curY] = 1;

	while(head <tail)
	{
		step ++;
		tmpTail = tail;
		for(int i=head;i<tail;i++) //一次访问 整个树的一层节点,非常巧妙
		{
			for(int j=0;j<8;j++)
			{
				curX = queue[i][0] + dir[j][0];
				curY = queue[i][1] + dir[j][1];
				if(matrix[curX][curY] != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8)
				{					
					queue[tmpTail][0] = curX;
					queue[tmpTail][1] = curY;
					tmpTail ++; // here we must add tmpTail after put node  in queue
					matrix[curX][curY] = 1;
					if(curX == endX && curY == endY)
						return step;
				}
			}
		}
		head = tail;
		tail = tmpTail; 
	}
	return -1;
}
int main()
{
	freopen("in.txt","r",stdin);
	int barrierCount;
	char c1,c2;
	scanf("%d\n",&barrierCount);
	for(int i=0;i<barrierCount;i++)
	{
		scanf("%c%c ",&c1,&c2);
		matrix[c1-'a'][c2-'1'] = 1;
	}
	scanf("%c%c\n",&c1,&c2);
	startX = c1 - 'a';
	startY = c2 - '1';
	scanf("%c%c\n",&c1,&c2);
	endX = c1 - 'a';
	endY = c2 - '1';
	printf("%d\n",specialBfs(startX,startY,endX,endY));
	fclose(stdin);
	return 0;
}

 

 

  • 大小: 208.7 KB
分享到:
评论

相关推荐

    knight 骑士征途C++算法实现

    骑士在国际象棋中是一种特殊的棋子,它的移动方式是每次跳动两格横向或纵向,再跳一格横向或纵向,形成一个"L"形的路径。在棋盘上,骑士的征途问题就是寻找骑士能够到达所有格子的最短路径。这个问题可以转换为图的...

    骑士周游问题qt实现

    骑士周游问题是一个经典的计算机科学问题,源自国际象棋中的骑士移动规则。在这个问题中,目标是找到一种方法,使得棋盘上的骑士能够从一个格子出发,经过棋盘上的每一个其他格子恰好一次,最后返回起点。在八皇后...

    8600骑士问题

    在解决8600骑士问题时,我们需要构建一个搜索算法的模型,其中广度优先搜索(BFS)算法是最为合适的选择。由于BFS能够保证在无权图中找到最短路径,它能够以一种系统化的方式遍历棋盘上所有可能的骑士移动路径。广度...

    C# 骑士游历 C# 骑士游历 winForm程序

    由于骑士的移动方式特殊,每次可以移动两行一列或两列一行,因此,解决这个问题通常采用深度优先搜索(DFS)或者广度优先搜索(BFS)。在C#中,可以利用递归或队列数据结构来实现这些搜索策略。 2. **C#基础**: ...

    matlab开发-KnightTour

    在编程领域,骑士之旅(KnightTour)是一个经典的算法问题,源于国际象棋的规则。MATLAB,作为一款强大的数值计算和符号计算软件,也是解决此类问题的理想工具。在这个项目中,我们将探讨如何使用MATLAB来解决骑士之...

    S1阶段项目JAVA骑士飞行棋

    棋子类应包含位置属性以及移动方法,该方法根据骑士的特殊移动规则(每次可移动两个单位的行进距离,然后转90度再移动一个单位)来确定可行的移动路径。 项目实施过程中,可能会涉及以下知识点: 1. **面向对象...

    数据结构13个经典问题

    迷宫问题通常涉及寻找从起点到终点的最短路径,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)解决。在实际编程中,可能会用到栈或队列,以及标记已访问节点的技术来避免死循环。 7. **骑士问题**: 骑士问题...

    checkio-task-shortest-knight-path:Checkio任务“最短的骑士之路”

    因此,要解决这个问题,我们需要理解这种特殊的移动规则,并能有效地在棋盘上寻找最优路径。 【标签】:“HTML” 虽然标签为"HTML",但这个任务更可能涉及到的是HTML作为页面展示的背景,实际解决问题则需要运用到...

    国际象棋马的遍历问题 mfc

    BFS 通常能保证找到最短的遍历路径,但在骑士巡游问题中,路径长度并不是关键因素,所以DFS和BFS在此问题上的表现没有明显优劣之分。 在实际编程实现中,我们需要维护一个记录已访问位置的数据结构,比如一个布尔...

    Knights-Travails:一个命令行程序,它将获取两组坐标,并返回它们在棋盘上为骑士所用的最短路径,以及骑士所采用的确切路径

    骑士走法在棋盘游戏中是一种特殊的移动方式,其规则是每次可以向前或向后移动两格,然后向左或向右移动一格,或者相反,形成一个"L"形的移动轨迹。 首先,我们需要理解骑士在棋盘上的移动规则。在国际象棋中,骑士...

    qishi.rar_马的遍历 问题

    骑士在国际象棋中是一种特殊的棋子,它的移动方式是跳跃式的,每次可以向前、后、左、右两个方向各移动两格,然后在另一个方向上再移动一格,形成一个"L"形的移动轨迹。因此,骑士的移动路径构成了一个非连续的网格...

    ACM 程序设计:图模型与搜索算法-p1.pdf

    对于骑士的移动,由于其遵循特殊的跳跃规则,邻接矩阵可能需要特殊处理,以反映骑士可以到达的所有八种可能的相邻格子。这将涉及在矩阵中正确地设置值,以便快速找出最短路径。 搜索算法在这种问题中扮演关键角色。...

    厦门大学软件工程系卓越工程师班算法分析与设计课程实验源码-内含源码和说明书.zip

    `字典序问题.cpp`可能使用了深度优先搜索或者BFS(广度优先搜索)策略。 8. **布线问题**:这可能是指电路板或网格上的最短路径问题,需要找到一条从起点到终点的路径,使得路径上的边的权重之和最小。`布线问题....

    knight_tour_generic.zip_The Knight_knight tour

    5. **动态规划**:虽然骑士之旅问题通常用搜索算法解决,但在某些特殊情况下,动态规划也可能发挥作用,例如预计算某些棋盘状态以优化搜索过程。 通过分析这个压缩包中的源代码,我们可以深入理解如何利用这些算法...

    The_Knights_Tour:如果将骑士放置在国际象棋棋盘上,那么骑士为了完全访问每个空间一次必须采取的动作顺序是什么?

    在国际象棋的棋盘游戏中,骑士是一种特殊的棋子,以其独特的“L”形移动模式而闻名。骑士之旅(The Knights Tour)是数学和象棋的一个经典问题,它挑战我们找到一种方法,使骑士能够依次经过棋盘上的所有64个格子,...

    马踏棋盘与八皇后问题

    在国际象棋中,骑士(Knight)是一种特殊的棋子,它可以按照“L”形的移动方式前进,即每次可以向前或向后移动两格,然后向左或向右移动一格,或者反之。马踏棋盘问题要求我们在一个8x8的棋盘上,让骑士依次走过每个...

    搜索算法及解题for oi

    4. **马的遍历问题**(骑士周游棋盘):这是另一种回溯问题,骑士在棋盘上移动,目标是访问到每个格子一次。解法通常使用深度优先搜索或广度优先搜索。 5. **加法分式分解**:涉及将一个数表示为若干个数的和,可以...

    搜索及其优化_杨志灿.pptx

    例如,双向BFS在解决骑士移动问题时,可以从起点和终点同时出发,通过哈希等方法连接路径。 在搜索过程中,剪枝是优化搜索效率的重要手段。可行性剪枝是在搜索过程中实时判断问题是否存在解,若不存在,则提前终止...

    c经典算法大全 word版本

    - **定义:** 巴斯卡三角形是一种特殊的数表,每行的数是上一行相邻两数的和。 - **性质:** - 第n行的第k个数等于组合数C(n,k),表示为n!/(k!(n-k)!). - 形状呈等腰三角形,边缘的数均为1。 - **应用场景:** 在...

    图算法例题1

    骑士在棋盘上移动的方式形成了一种特殊的图结构,每个格子都是一个节点,而骑士可能的下一步对应于边。计算骑士的所有可能移动可以帮助我们理解图遍历的问题。 4. **有向图边的分类**:问题1005讨论了有向图中边的...

Global site tag (gtag.js) - Google Analytics