main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 77 行

/*********************************************************************************
24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班，
 向东要走Ｍ块，向北要走Ｎ块，（见图）。请设计一个程序，由计算机寻找并
 打印出所有的上班的路径。

                                               单位

           ┬   ┌─┬─┬─┬─┬─┬─┬─┐
           │   │  │  │  │  │  │  │  │
           │   ├─┼─┼─┼─┼─┼─┼─┤
           ↓   │  │  │  │  │  │  │  │
           Ｎ   ├─┼─┼─┼─┼─┼─┼─┤
           ↑   │  │  │  │  │  │  │  │
           │   ├─┼─┼─┼─┼─┼─┼─┤
           │   │  │  │  │  │  │  │  │
           ┴   └─┴─┴─┴─┴─┴─┴─┘
           家   ├─────→Ｍ←─────┤

分析:	只能向上和向右走,否则会走回头路;按照这样算,此人只要走M+N块就可以到达单位了;
		因此,只能有两个方向走,每走一块,到达一个新地点,从新地点到单位是本问题的一个
		子问题,所以此问题可以分为两个子问题;
	    采用分治算法
**********************************************************************************/

#include <stdio.h>

#define M 7
#define N 4

typedef struct
{
	int x;
	int y;
}Pos;

//保存路径(包括起点)
Pos path[M+N+1];

int counter = 0;

FILE* fp;

void move(int x, int y, int i)
{
	if(x>M || y>N)
		return;
	else 
	{
		//如果合法,记录地点
		path[i].x = x;
		path[i].y = y;
		if(x==M && y==N)//如果已经到达单位,输出
		{
			int k;

			counter++;//计算路径总数
			for(k=0; k<M+N+1; k++)
				//printf(" (%d,%d) ",path[k].x,path[k].y);
				fprintf(fp," (%d,%d) ",path[k].x,path[k].y);//输出到文件
			fprintf(fp,"\n");
		}
		else
		{
			i++;
			move(x+1,y,i);//分治
			move(x,y+1,i);//分治
		}
	}
}

void main()
{
	fp = fopen("path.txt","w");
	move(0,0,0);
	fprintf(fp,"一共有%d条路径!\n",counter);
	fclose(fp);
}