• 热门专题

DFS解马走日问题

作者:  发布日期:2015-08-25 21:38:09
Tag标签:问题  解马走  
  • 问题描述

    在n*n的棋盘中,马只能走"日"字。马从位置(0,0)出发,把棋盘的每一格都走一次且只走一次。找出所有路径。 5*5的棋盘上,有304种解。

    问题分析
    搜索过程是从(0,0)出发,按照深度优先的原则,从8个方向中尝试一个可以走的点,直到尝试过所有的方向,走完棋盘上的所有点,得出所有的解。

    马走日问题可以看成是在层数为n*n的8叉树中,找出所有的解。

     

    #include "stdio"
    
    int N =5;//棋盘大小为5*5
    int martic[N][N];//代表棋盘的数组
    int count = 0;//走的步数
    int solution = 0;//方法数量
    int step[8][2] = {{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//要走的八个方向
    
    int isok(int x,int y)//判断这一步是否符合规则
    {
    	if ((x>=0&&x<N&&y>=0&&y<N&&martic == 0))
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    void display()//如果整个棋盘已经走满,就输出整个棋盘
    {
    	printf("the %d solution:
    ",++solution);
    	for(int i = 0;i < N;i++)
    	{
    		for(int j = 0;j < N;j++)
    		{
    			printf("%d  ",martic[i][j]);
    		}
    		printf("
    ");
    	}	
    }
    
    void DFS(int x,int y)
    {
    	int nextx,nexty;
    	for (int i = 0; i < 8; ++i)
    	{
    		nextx = x + step[i][0];
    		nexty = y + step[i][1];
    
    		if (isok(nextx,nexty))//发现
    		{
    			
    			if (count != (N*N-1))
    			{
    				count++;
    				martic[nextx][nexty] = count;
    				DFS(nextx,nexty);//递进 和 回溯
    				martic[nextx][nexty] = 0;
    				count--;
    			}
    			else
    			{
    				display();//满足条件,输出
    			}
    		}
    	}}
    
    int int main(int argc, char const *argv[])
    {
    	count = 1;
    	martic[0][0] = 1;
    	DFS(0,0);
    	return 0;
    }
    


     


     


     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规