main.cpp

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

/******************************************************************************

71. (最长连线) 设有一个 N×N 的方格图形，且 N 为 3 的倍数。要求在图形中
 存放 0 或 1，相邻的 1 可以连成一条连线，连接的方法可以是行，也可以是列；
 同时约定一条连线只能有一个起点和一个终点，图形上的点最多只能访问一次。
 编程求最长连线. 例如 N＝6 时，有下图：
                 １  ２  ３  ４  ５  ６
               ┌─┬─┬─┬─┬─┬─┐
           １  │１│１│１│０│０│１│
               ├─┼─┼─┼─┼─┼─┤
           ２  │１│１│０│１│１│１│
               ├─┼─┼─┼─┼─┼─┤
           ３  │０│０│０│１│０│１│
               ├─┼─┼─┼─┼─┼─┤
           ４  │１│１│０│１│１│１│
               ├─┼─┼─┼─┼─┼─┤
           ５  │０│１│０│０│０│０│
               ├─┼─┼─┼─┼─┼─┤
           ６  │１│１│１│１│０│０│
               └─┴─┴─┴─┴─┴─┘
   在该图中，包含有如下的一些连线：
     １←１←１        １←１                     １
     ↓                ↓                         ↓
     １→１            １                 １→１  １
                       ↓                 ↑      ↓
                       １→１→１         １      １
                                          ↑      ↓
                                          １←１←１
    在以上的连线中，最长的连线为：    表示方法：
             １                       最长连线长度：LMAX=9
             ↓                       连线：(1,6)→(2,6)→
     １→１  １                             (3,6)→(4,6)→
     ↑      ↓                             (4,5)→(4,4)→
     １      １                             (3,4)→(2,4)→
     ↑      ↓                             (2,5)
     １←１←１                  连线的表示不是唯一的，仅给出一种即可。

  *****************************************************************************/
/*
//分治法求解
#include <stdio.h>

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

#define N 6

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};


int map[N][N] = {1,1,1,0,0,1,
                 1,1,0,1,1,1,
				 0,0,0,1,0,1,
				 1,1,0,1,1,1,
				 0,1,0,0,0,0,
				 1,1,1,1,0,0};

Pos Line[N*N];
Pos MaxLine[N*N];

//连线
void join(int x, int y, int k, int *pmax)
{
	int i;	
	Line[k].x = x;
	Line[k].y = y;
	map[y][x] = 0;
	for(i=0; i<4; i++)//分治
	{	
		#define CHECKED(x,y) x>=0 && x<N && y>=0 && y<N && map[y][x] == 1
		if(CHECKED(x+dx[i],y+dy[i]))
		{
			join(x+dx[i],y+dy[i],k+1,pmax);
		}
	}
	map[y][x] = 1;
	//找到一条路径
	if(k+1 > *pmax)
	{
		int t;
		*pmax = k+1;
		for(t=0; t<=*pmax; t++)
			MaxLine[t] = Line[t];
	}
}

//打印路径
void PrintMaxLine(int max)
{
	int i;
	printf("max = %d\n",max);
	for(i=0; i<max; i++)
	{
		printf("(%d , %d) ",MaxLine[i].x+1,MaxLine[i].y+1);
	}	
	printf("\n");
}

void main()
{
	int x,y;
	int max = 0;
	for(y=0; y<N; y++)
	{
		for(x=0; x<N; x++)
		{
			if(map[y][x] == 1)
				join(x,y,0,&max);		
		}
	}
	PrintMaxLine(max);
}
*/

//用回溯法求解
#include <stdio.h>

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

#define N 6

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int map[N][N] = {1,1,1,0,0,1,
                 1,1,0,1,1,1,
				 0,0,0,1,0,1,
				 1,1,0,1,1,1,
				 0,1,0,0,0,0,
				 1,1,1,1,0,0};

Pos Line[N*N];
Pos MaxLine[N*N];
int path[N*N];
int join(int x, int y)
{
	int k;
	int max = 0;

	if(map[y][x] == 0)
		return 0;

	Line[0].x = x;
	Line[0].y = y;
	for(k=0; k<N*N; k++)
		path[k] = -1;
	
	map[y][x] = 0;
	k = 0;
	while(k>=0)
	{
		while(++path[k]<4)
		{
			int tx,ty;
			tx = x + dx[path[k]];
			ty = y + dy[path[k]];
			if(tx>=0 && tx<N && ty>=0 && ty<N && map[ty][tx] == 1)
			{
				map[y][x] = 0;
				x = tx;
				y = ty;
				k++;
			}
		}
		//找到从该点出发的一条路径
		if(max < k)//如果大于当前最大长度,保存
		{
			int i;
			max = k;
			for(i=0; i<max; i++)
			{
				//保存从该点出发的最长路径
				Line[i+1].x = Line[i].x + dx[path[i]];
				Line[i+1].y = Line[i].y + dy[path[i]];
			}
		}
		//回溯
		map[y][x] = 1;
		path[k] = -1;
		k--;
		if(k<0)
		{
			break;
		}
		x = x - dx[path[k]];
		y = y - dy[path[k]];
	}
	map[y][x] = 1;

	return max;
}

void PrintMaxLine(int max)
{
	int i;
	printf("max = %d\n",max+1);
	for(i=0; i<=max; i++)
	{
		printf("(%d,%d) ",MaxLine[i].x+1,MaxLine[i].y+1);
	}
	printf("\n");
}

void main()
{
	int len;
	int x, y;
	int max = 0;
	for(y=0; y<N; y++)
	{
		for(x=0; x<N; x++)
		{
				len = join(x,y);
				if(max < len)
				{
					int i;
					max = len;
					for(i=0; i<=max; i++)
						MaxLine[i] = Line[i];
				}
		}
	}
	PrintMaxLine(max);	
}