【C 语言】DFS 解决马最少跳步次数

怼烎@ 2022-08-07 17:59 176阅读 0赞

一道简单的C 语言题目， 给定特定长宽的矩形，给定起点终点，问最少几次可以从起点跳到终点。

要求 必须按照象棋中马的跳走方式，如果不能跳到，则输出 -1

分析：

两种方法：

1. BFS，将一次跳跃到达的位置，存入队列中，再通过出队检查是否是终点。

如果不是终点，继续将出队点八个方向的点入队，直到找到终点位置。

2. DFS，DFS的思路比较简单，但较好费资源。遍历出所有可以到达终点的线路，并比较求取最小的步数。

BFS 比较简单就不列出代码了，以下列出 DFS的代码：

<span style="font-size:18px;">#include <stdio.h>
    #include <string.h>
    
    #define MAX_SIZE 100
    int column;
    int eX;
    int eY;
    int result = 99999;
    int bVisited[MAX_SIZE][MAX_SIZE];
    
    const int offset[8][2] = {
       {1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
    
    void dfs( int x, int y,int step);
    
    int main(void)
    {
    	int tc, T;
    
    //	freopen("input.txt", "r", stdin);
    	setbuf(stdout, NULL);
    
    	scanf("%d", &T);
    	for(tc = 0; tc < T; tc++)
    	{
    		int sX;
    		int sY;
    
    		scanf("%d %d",&row,&column);
    		scanf("%d %d %d %d",&sX,&sY,&eX,&eY);
    
    		result = 99999;
    		memset(bVisited,0,sizeof(bVisited));
    
    		bVisited[sX][sY] = 1;
    		dfs(sX,sY,0);
    
    		if (result == 99999)
    			result = -1;
    
    		printf("%d\n",result);
    	}
    
    	return 0;
    }
    
    void dfs( int x, int y,int step)
    {
    	int i = 0;
    	bVisited[x][y] = step;
    
    	if (x == eX && y == eY)
    	{
    		result = result > step ? step : result;
    		return;
    	}
    
    	for ( i = 0; i < 8; i++ )
    	{
    		int a = x+offset[i][0];
    		int b = y+offset[i][1];
    
    		if (	a >= 1 && a <= row &&
    				b >= 1 && b <= column &&
    				( !bVisited[a][b] || bVisited[a][b] > step+1))
    		{
    			dfs(a,b,step+1);
    		}
    	}
    }
    </span>

此处，比较难想的是，DFS 函数中的判断条件，给定 bVisited\[a\]\[b\] = step ，判断如果 当前的 bVisited\[a\]\[b\] 值是大于 step+1 的，说明 这个点以前被访问过，但这次访问的数据明显比上次少，所以需要继续 DFS，如此就可以列举出来所有的情况。