数据结构-青蛙找家

以你之姓@ 2022-05-19 07:43 116阅读 0赞

***【题目来自灰灰考研】***

**拓展题目：**在一个 5\*5 的地图上，一只蛤欲从起点跳到目的地。中间有一条河（如图），但这只蛤不会游泳，并且每次只能横着跳一格或竖着跳一格。（聪明的蛤不会跳已经跳过的路）

（1） 总共有多少种跳法。

（2） 给出路径最短的跳法。

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1][]

#include<iostream>
    #include<cstdlib>
    #include<cstring>
    #define MIN 0xc0c0c0c0
    #define MAX 0x3f3f3f3f
    using namespace std; 
    
    
    const int n = 5, m = 5;//定义问题规模 
    int solutionNumber = 0;//问题解法数量 
    int totalSteps = MAX;
    int tX = 4, tY = 4;
    int visit[n][m];//map表示整个地图，trace记录路径，visit用来记录当前点是否被走过 
    int moveDirection[][2] = {1, 0, -1, 0, 0, 1, 0, -1};//下一步相对于当前位置的偏移量 
    
    typedef struct{
    	/*
    		定义一个结构体，用来存储路径每一步的坐标 
    	*/
    	int x, y;
    }TraceNode[n*m];
    
    TraceNode path;
    
    bool CanJump(int x, int y)
    {
    	/*
    		判断当前位置是否合法，其中要注意第三行只有第三个位置可以通过 
    	*/ 
    	if(x < 0 || x >= n || y < 0 || y >= m)
    		return false;
    	if(x == 2 && y != 2)
    		return false;
    	return true;
    }
    
    void GetBestSolution(int x, int y, int step)
    {
    	if(x == tX && y == tY)
    	{
    		/*
    			回溯出口，到达目的地
    			此时需要增加一次解法数量
    			同时看是否需要更新最优解 
    		*/ 
    		solutionNumber++;
    		if(totalSteps > step)
    			totalSteps = step;
    		return;
    	}
    	int nextX, nextY;
    	for(int i = 0; i < 4; i++)
    	{
    		nextX = x + moveDirection[i][0];
    		nextY = y + moveDirection[i][1];
    		if(!CanJump(nextX, nextY))
    			continue;
    		
    		if(visit[nextX][nextY] == 0)
    		{
    			visit[nextX][nextY] = 1;
    			GetBestSolution(nextX, nextY, step + 1);
    			visit[nextX][nextY] = 0;
    		}
    	}
    }
    
    void PrintTrace(int x, int y, int step) 
    {
    	/*
    		再来执行一遍，寻找最优解的路径 
    	*/ 
    	path[step].x = x;
    	path[step].y = y;
    	if(x == tX && y == tY)
    	{
    		if(totalSteps == step)
    		{
    			//找到最优解，打印路径 
    			for(int i = 0; i < step; i++)
    			{
    				cout<<"("<<path[i].x<<","<<path[i].y<<")"<<"-->";
    			}
    			cout<<"("<<path[step].x<<","<<path[step].y<<")"<<endl;
    		}
    		return;
    	}
    	int nextX, nextY;
    	for(int i = 0; i < 4; i++)
    	{
    		nextX = x + moveDirection[i][0];
    		nextY = y + moveDirection[i][1];
    		if(!CanJump(nextX, nextY))
    			continue;
    		if(visit[nextX][nextY] == 0)
    		{
    			visit[nextX][nextY] = 1;
    			PrintTrace(nextX, nextY, step + 1);
    			visit[nextX][nextY] = 0;
    		}
    	}
    }
    int main()
    {
    	memset(visit, 0, sizeof(visit));
    	int x = 0, y = 0;
    	visit[x][y] = 1;
    	GetBestSolution(x, y, 0); 
    	cout<<"The Total Solution Number is:"<<solutionNumber<<endl;
    	
    	cout<<"The Best Solution Step Number is:"<<totalSteps<<endl;
    	
    	cout<<"The Trace is:"<<endl;
    	
    	memset(visit, 0, sizeof(visit));
    	visit[x][y] = 1;
    	PrintTrace(x, y, 0);
    	return 0;
    }

[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220519/e1f6145dbf2641d1bc9eb01e436f1e3e.png