马的遍历问题

布满荆棘的人生 2022-08-03 00:16 195阅读 0赞

[![Flag Counter][]][Flag Counter 1]

在10\*9的中国象棋的棋盘中，马只能走“日”字，不考虑蹩脚。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次，设计程序求解。

// horse_traverse.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<iostream>
    
    using namespace std;
    
    typedef unsigned char BYTE;
    //#define Width 9
    //#define Height 10
    #define Width 6
    #define Height 6
    struct Position
    {
    	BYTE x;
    	BYTE y;
    };
    
    
    int map[Height][Width] = { 0 };
    vector<vector<Position>>record;
    vector<Position>solution;
    bool valid_shift(BYTE x, BYTE y)
    {
    	vector<Position>aa;
    	Position pos;
    	
    	if (x + 1 < Width&&y - 2 >= 0 && map[y-2][x+1] == 0)//direct 0
    	{
    		pos.x = x + 1;
    		pos.y = y - 2;
    		aa.push_back(pos);
    	}
    	if (x + 2 < Width&&y - 1 >= 0 && map[y-1][x+2] == 0)//direct 1
    	{
    		pos.x = x + 2;
    		pos.y = y - 1;
    		aa.push_back(pos);
    		
    	}
    	if (x + 2 < Width&&y + 1 < Height && map[y+1][x+2] == 0)//direct 2
    	{
    		pos.x = x + 2;
    		pos.y = y +1;
    		aa.push_back(pos); 
    	}
    	if (x + 1 < Width&&y + 2 < Height && map[y+2][x+1] == 0)//direct 3
    	{
    		pos.x = x + 1;
    		pos.y = y +2;
    		aa.push_back(pos);
    	}
    	if (x - 1 >= 0 && y + 2 < Height && map[y+2][x-1] == 0)//direct 4
    	{
    		pos.x = x -1;
    		pos.y = y + 2;
    		aa.push_back(pos); 
    	}
    	if (x - 2 >= 0 && y + 1 < Height && map[y+1][x-2] == 0)//direct 5
    	{
    		pos.x = x -2;
    		pos.y = y + 1;
    		aa.push_back(pos); 
    	}
    	if (x - 2 >= 0 && y -1 >= 0 && map[y-1][x-2] == 0)//direct 4
    	{
    		pos.x = x - 2;
    		pos.y = y -1;
    		aa.push_back(pos);
    	}
    	if (x - 1 >= 0 && y - 2 >= 0 && map[y-2][x-1] == 0)//direct 4
    	{
    		pos.x = x - 1;
    		pos.y = y - 2;
    		aa.push_back(pos);
    	}
    	if (!aa.empty())
    	{
    		record.push_back(aa);
    		return true;
    	}
    	return false;
    }
    
    bool isSuccess()
    {
    	int sum = 0;
    	vector<vector<Position>>::iterator it;
    	for (int i = 0; i < Width; i++)
    		for (int j = 0; j < Height; j++)
    		{
    		sum += map[j][i];
    		}
    	it = record.end() - 1;
    	int x = (*((*it).end() - 1)).x;
    	int y = (*((*it).end() - 1)).y;
    	if (sum == Width*Height - 1 && map[y][x] == 0)
    		return true;
    	return false;
    
    }
    
    
    bool horse_traverse(BYTE x, BYTE y)
    {
    
    	Position pos;
    	vector<vector<Position>>::iterator it;
    	vector<Position>::iterator it1, it2;
    	map[y][x] = 1;
    	valid_shift(x, y);
    	while (!record.empty())
    	{
    		it = record.end() - 1;
    		it1 = (*it).end() - 1;
    		bool flag = false;
    		while (!valid_shift((*it1).x, (*it1).y))
    		{
    			(*it).pop_back();
    			if ((*it).empty())
    			{
    				while ((*it).empty())
    				{
    					record.pop_back();
    					if (record.empty())
    					{
    						return false;
    					}
    					it = record.end() - 1;
    					(*it).pop_back();
    					it2 = solution.end() - 1;
    					map[(*it2).y][(*it2).x] = 0;
    					solution.pop_back();
    				}
    				
    				flag = true;
    				break;
    			}
    			it1 = (*it).end() - 1;
    		}
    		if (!flag)
    		{
    			it = record.end() - 1;
    			bool flag1 = false;
    			if ((*it).size() == 1 && (*(it - 1)).size() == 1)//这里要防止马在两个格子之间来回跳的情况发生
    			{
    				vector<Position>aa;
    				Position pos;
    
    				int x = (*it)[0].x;
    				int y = (*it)[0].y;
    				map[(*(it - 1))[0].y][(*(it - 1))[0].x] = 1;
    				if (x + 1 < Width&&y - 2 >= 0 && map[y - 2][x + 1] == 0)//direct 0
    				{
    					pos.x = x + 1;
    					pos.y = y - 2;
    					aa.push_back(pos);
    
    				}
    				if (x + 2 < Width&&y - 1 >= 0 && map[y - 1][x + 2] == 0)//direct 1
    				{
    					pos.x = x + 2;
    					pos.y = y - 1;
    					aa.push_back(pos);
    
    				}
    				if (x + 2 < Width&&y + 1 < Height && map[y + 1][x + 2] == 0)//direct 2
    				{
    					pos.x = x + 2;
    					pos.y = y + 1;
    					aa.push_back(pos);
    				}
    				if (x + 1 < Width&&y + 2 < Height && map[y + 2][x + 1] == 0)//direct 3
    				{
    					pos.x = x + 1;
    					pos.y = y + 2;
    					aa.push_back(pos);
    				}
    				if (x - 1 >= 0 && y + 2 < Height && map[y + 2][x - 1] == 0)//direct 4
    				{
    					pos.x = x - 1;
    					pos.y = y + 2;
    					aa.push_back(pos);
    				}
    				if (x - 2 >= 0 && y + 1 < Height && map[y + 1][x - 2] == 0)//direct 5
    				{
    					pos.x = x - 2;
    					pos.y = y + 1;
    					aa.push_back(pos);
    				}
    				if (x - 2 >= 0 && y - 1 >= 0 && map[y - 1][x - 2] == 0)//direct 6
    				{
    					pos.x = x - 2;
    					pos.y = y - 1;
    					aa.push_back(pos);
    				}
    				if (x - 1 >= 0 && y - 2 >= 0 && map[y - 2][x - 1] == 0)//direct 7
    				{
    					pos.x = x - 1;
    					pos.y = y - 2;
    					aa.push_back(pos);
    				}
    
    				if (aa.size() == 1 && aa[0].x == (*(it - 1))[0].x&&aa[0].y == (*(it - 1))[0].y)
    				{
    					record.pop_back();
    					record.pop_back();
    					it = record.end() - 1;
    					(*it).pop_back();
    					if ((*it).size() == 0)
    						record.pop_back();
    					it1 = solution.end() - 1;
    					map[(*it1).y][(*it1).x] = 0;
    					solution.pop_back();
    					flag1 = true;
    				}
    
    			}
    			if (!flag1)
    			{
    				solution.push_back(*it1);
    				map[(*it1).y][(*it1).x] = 1;
    			}
    		}
    		if (isSuccess())
    		{
    			it = record.end() - 1;
    			solution.push_back(*((*it).end() - 1));
    			return true;
    		}
    	}
    
    
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
    	horse_traverse(0, 2);
    	
    	system("pause");
    	return 0;
    }

没有优化，计算量惊人。

开始以为程序有问题导致陷入死循环，后来发现可以运行得出结果，只是太！！！慢！！！了！！！！！！！！！！！！！！！！！

后面有时间重新写一个。

[Flag Counter]: /images/20220731/9045e167c6794fad91f3ab3cdbd4bc14.png
[Flag Counter 1]: http://s11.flagcounter.com/more/RPv