C：“走马”的路径问题（回溯）

前言

递归回溯问题，不是马踏棋盘

正文

有一个中国象棋中的“马”，在半张棋盘的左上角出发，右下角跳去。规定只允许向右跳（可上，可下，但不允许向左跳）求从起点A（1,1）到终点B（m,n）共有多少种不同的跳法 分析：和dfs找多条路径类似，但是限定了“马”的走向和边界，用两个数组dx[4]，dy[4]控制每次走的方向，找到一条路径后返回，回溯的时候把经过的点置0，因为一个点又多条路径可选，可以继续找该点的另条到达终点的路径。 图的多条简单路径

代码

#include <stdio.h> static int chessboard[5][9]={0}; //储存半个棋盘的二维数组 static int count=0; const int dx[4]={2,1,-1,-2};//横坐标的变化 const int dy[4]={1,2,2,1}; //纵坐标的变化 void horse_count(int srcx,int srcy,int destx,int desty){ if(srcx>=0&&srcx<5&&srcy>=0&&srcy<9&&chessboard[srcx][srcy]==0){ //规定边界和不重复路线 if(srcx==destx-1&&srcy==desty-1){ //达到目的地 count++; //次数加1，返回 return ; } chessboard[srcx][srcy]=1; //标记走过的点 int i; for(i=0;i<4;i++){ //四个方向依次进行dfs搜索 horse_count(srcx+dx[i],srcy+dy[i],destx,desty); } chessboard[srcx][srcy]=0; //回溯置0可以接着找其他路径 } } int main(){ int m,n; scanf("%d %d",&m,&n); horse_count(0,0,m,n); printf("%d",count); return 0; }