1 0 1 1 0 1 0 0 1 1
1 1 1 0 1 1 1 1 0 1
1 1 1 1 1 1 1 1 0 1
0 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 0 0 0 1 1 0 0
1 1 1 1 0 1 1 1 1 0
1 1 1 0 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
1 0 1 1 0 0 0 1 0 1

一条线能最多将上面矩阵（随机生成）中的多少个1联起来？
线不能交叉。假定从矩阵第一个元素开始。可以横、竖、斜相连，不能联到0。

我的程序只能达到如下效果（0*->1*->2*->....->67*），再迭代就没有效率了，时间上就不可忍受了。

0* 0 3* 4* 0 12* 0 0 18* 19*
1* 2* 5* 0 11* 13* 16* 17* 0 20*
7* 6* 9* 10* 14* 15* 24* 23* 0 21*
0 8* 28* 0 0 25* 0 0 22* 1
30* 29* 32* 27* 26* 54* 53* 52* 51* 0
0 31* 33* 0 0 0 55* 50* 0 0
35* 34* 38* 39* 0 48* 49* 56* 62* 0
36* 37* 40* 0 47* 58* 57* 61* 63* 0
0 41* 42* 43* 46* 59* 60* 64* 66* 0
1 0 44* 45* 0 0 0 65* 0 67*

[此贴子已经被作者于2006-5-16 19:37:07编辑过]

#include "windows.h"
#include "stdlib.h"
#include "stdio.h"

typedef int INT32;
typedef unsigned int UINT32;
typedef unsigned char UINT8;
typedef signed char INT8;
typedef unsigned short UINT16;
typedef signed short INT16;

#define SUCCESS 1
#define FAIL -1
#define TRUE 1
#define FALSE 0
#define MAX_NEIGHBOR_NUMBER 8
#define MAX_MAP_SIZE_X 10
#define MAX_MAP_SIZE_Y 10
#define MAX_STEP_NUM MAX_MAP_SIZE_X*MAX_MAP_SIZE_Y
#define START_X 0
#define START_Y 0

typedef struct _NODE_STRUCT_
{
UINT8 ucValue;
BOOL bVisited;
UINT8 ucNeighborNum;
void *apNeighbor[MAX_NEIGHBOR_NUMBER];
UINT8 ucLable_X;
UINT8 ucLable_Y;
}NODE_STRUCT;

typedef struct _TRACE_STRUCT_
{
UINT8 ucStepNum;
struct
{
UINT8 ucLable_X;
UINT8 ucLable_Y;
}astStep[MAX_STEP_NUM];
}TRACE_STRUCT;

typedef struct _RETURN_LOCATION_STRUCT_
{
UINT8 ucLable_X;
UINT8 ucLable_Y;
}RETURN_LOCATION_STRUCT;

TRACE_STRUCT gstStep;
TRACE_STRUCT gstStep_max;
NODE_STRUCT gastMap[MAX_MAP_SIZE_X][MAX_MAP_SIZE_Y];
NODE_STRUCT gastMap_Temp[MAX_MAP_SIZE_X][MAX_MAP_SIZE_Y];
UINT8 gucTraceNodeNumber;
RETURN_LOCATION_STRUCT gstReturnLoction;
UINT32 guiiterative = 0;
UINT32 guiReturnNum = 0;

void print_step(TRACE_STRUCT *vpstStep);
void Get_Return_Location();

void Init_Node_Neighbor()
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;
UINT8 ucNeighborNum;

for(ucLable_X = 0; ucLable_X < MAX_MAP_SIZE_X; ucLable_X++ )
{
for(ucLable_Y = 0; ucLable_Y < MAX_MAP_SIZE_Y; ucLable_Y++)
{
gastMap[ucLable_X][ucLable_Y].ucLable_X = ucLable_X;
gastMap[ucLable_X][ucLable_Y].ucLable_Y = ucLable_Y;
if (0 == gastMap[ucLable_X][ucLable_Y].ucValue)
{
gastMap[ucLable_X][ucLable_Y].ucNeighborNum = 0;
continue;
}
ucNeighborNum = 0;

/*7 left up*/
if (ucLable_X > 0 && ucLable_Y > 0 )
{
if (1 == gastMap[ucLable_X-1][ucLable_Y-1].ucValue)
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X-1][ucLable_Y-1];
ucNeighborNum++;
}
}

/*1 up*/
if ( ucLable_X > 0 )
{
if (1 == gastMap[ucLable_X-1][ucLable_Y].ucValue )
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X-1][ucLable_Y];
ucNeighborNum++;
}
}

/*2 left*/
if (ucLable_Y > 0 )
{
if (1 == gastMap[ucLable_X][ucLable_Y-1].ucValue )
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X][ucLable_Y-1];
ucNeighborNum++;
}
}

/*8 right up*/
if ( ucLable_Y < MAX_MAP_SIZE_Y-1&&ucLable_X > 0 )
{
if (1 == gastMap[ucLable_X-1][ucLable_Y+1].ucValue)
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X-1][ucLable_Y+1];
ucNeighborNum++;
}
}

/*6 left down*/
if (ucLable_Y > 0 && ucLable_X < MAX_MAP_SIZE_X-1)
{
if (1 == gastMap[ucLable_X+1][ucLable_Y-1].ucValue)
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X+1][ucLable_Y-1];
ucNeighborNum++;
}
}

/*3 right*/
if (ucLable_Y < MAX_MAP_SIZE_Y-1)
{
if (1 == gastMap[ucLable_X][ucLable_Y+1].ucValue )
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X][ucLable_Y+1];
ucNeighborNum++;
}
}

/*4 down*/
if (ucLable_X < MAX_MAP_SIZE_X-1)
{
if (1 == gastMap[ucLable_X+1][ucLable_Y].ucValue )
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X+1][ucLable_Y];
ucNeighborNum++;
}
}

/*5 right down*/
if (ucLable_X < MAX_MAP_SIZE_X-1&&ucLable_Y < MAX_MAP_SIZE_Y-1)
{
if (1 == gastMap[ucLable_X+1][ucLable_Y+1].ucValue)
{
gastMap[ucLable_X][ucLable_Y].apNeighbor[ucNeighborNum] = &gastMap[ucLable_X+1][ucLable_Y+1];
ucNeighborNum++;
}
}

gastMap[ucLable_X][ucLable_Y].ucNeighborNum = ucNeighborNum;
}
}

return;
}

void Init_Trace_Node()
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;

gucTraceNodeNumber = 0;

for(ucLable_X = 0; ucLable_X < MAX_MAP_SIZE_X; ucLable_X++ )
{
for(ucLable_Y = 0; ucLable_Y < MAX_MAP_SIZE_Y; ucLable_Y++)
{
/*
if (0 == ucLable_X ||(MAX_MAP_SIZE-1)==ucLable_X||ucLable_X==ucLable_Y
|| ucLable_X==(MAX_MAP_SIZE-ucLable_Y-1))
{*/

if (rand()%10 < 7)
{
gastMap[ucLable_X][ucLable_Y].ucValue = 1;
gastMap[ucLable_X][ucLable_Y].bVisited = FALSE;

}
else
{
gastMap[ucLable_X][ucLable_Y].ucValue = 0;
}

if (1 == gastMap[ucLable_X][ucLable_Y].ucValue)
{
gucTraceNodeNumber++;
}

/*}*/


}
}
if (0 == gastMap[0][0].ucValue)
{
gastMap[0][0].ucValue = 1;
gucTraceNodeNumber++;
}
printf("max node number is %d\n",gucTraceNodeNumber);
return;
}

INT8 Get_Next_Step( UINT8 vucLable_X,UINT8 vucLable_Y)
{
UINT8 ucLoop = 0;
NODE_STRUCT *pstNode = NULL;
UINT8 ucNeighborNum = gastMap[vucLable_X][vucLable_Y].ucNeighborNum;
INT8 cResult = FAIL;

gastMap[vucLable_X][vucLable_Y].bVisited = TRUE;
gstStep.astStep[gstStep.ucStepNum].ucLable_X = vucLable_X;
gstStep.astStep[gstStep.ucStepNum].ucLable_Y = vucLable_Y;
gstStep.ucStepNum++;
gucTraceNodeNumber--;

for(ucLoop = 0;ucLoop < ucNeighborNum; ucLoop++)
{
pstNode = gastMap[vucLable_X][vucLable_Y].apNeighbor[ucLoop];
if (1 == pstNode->ucValue && FALSE == pstNode->bVisited)
{
cResult = Get_Next_Step(pstNode->ucLable_X,pstNode->ucLable_Y);
if (SUCCESS != cResult)
{
if (MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y)
{
return SUCCESS;
}
else if (gstReturnLoction.ucLable_X != vucLable_X
||gstReturnLoction.ucLable_Y != vucLable_Y)
{

gucTraceNodeNumber++;
gstStep.ucStepNum--;
gastMap[vucLable_X][vucLable_Y].bVisited = FALSE;
guiReturnNum++;
/*printf("\rX=%d,Y=%d",gstReturnLoction.ucLable_X,gstReturnLoction.ucLable_Y);*/
return FAIL;

}
else
{
continue;
}
}
else
{
return SUCCESS;
}


}
}

if (gstStep_max.ucStepNum == gstStep.ucStepNum)
{
memcpy(&gstStep_max,&gstStep,sizeof(TRACE_STRUCT));
//print_step(&gstStep_max);
//printf("number of iterative is:%d\r",guiiterative);
}
if (gstStep_max.ucStepNum < gstStep.ucStepNum)
{
memcpy(&gstStep_max,&gstStep,sizeof(TRACE_STRUCT));
print_step(&gstStep_max);
printf("number of iterative is:%d\r",guiiterative);
/*printf("\nx=%d,y=%d\n",gstReturnLoction.ucLable_X,gstReturnLoction.ucLable_Y);*/
}

if (0 == gucTraceNodeNumber )
{
return SUCCESS ;
}
gucTraceNodeNumber++;
Get_Return_Location();
gstStep.ucStepNum--;
gastMap[vucLable_X][vucLable_Y].bVisited = FALSE;

guiiterative++;

return FAIL;
}

void print_step(TRACE_STRUCT *vpstStep)
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;
UINT8 ucloop = 0;
printf("\n\n\n\n");
for(ucLable_X = 0; ucLable_X < MAX_MAP_SIZE_X; ucLable_X++)
{
for(ucLable_Y = 0; ucLable_Y < MAX_MAP_SIZE_Y; ucLable_Y++)
{
for(ucloop = 0; ucloop < vpstStep->ucStepNum; ucloop++)
{
if (vpstStep->astStep[ucloop].ucLable_X == ucLable_X
&&vpstStep->astStep[ucloop].ucLable_Y == ucLable_Y)
{
printf(" %3d* ",ucloop);
break;
}
}
if (ucloop >= vpstStep->ucStepNum)
{
printf(" %3d ",gastMap[ucLable_X][ucLable_Y].ucValue);
}

}
printf("\n");
}
printf("\n");
return;
}

void print_map()
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;
printf("\n");
for(ucLable_X = 0; ucLable_X < MAX_MAP_SIZE_X; ucLable_X++)
{
for(ucLable_Y = 0; ucLable_Y < MAX_MAP_SIZE_Y; ucLable_Y++)
{

printf("%3d",gastMap[ucLable_X][ucLable_Y].ucValue);

}
printf("\n");
}
printf("\n");
return;
}

void Delete_Isolated_Point()
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;
UINT8 ucOneWayNodeNum = 0;
printf("\n");
for(ucLable_X = 0; ucLable_X < MAX_MAP_SIZE_X; ucLable_X++)
{
for(ucLable_Y = 0; ucLable_Y < MAX_MAP_SIZE_Y; ucLable_Y++)
{
if ( 0 == gastMap[ucLable_X][ucLable_Y].ucNeighborNum
&& 1 == gastMap[ucLable_X][ucLable_Y].ucValue)
{
gucTraceNodeNumber--;
}
if ( 1 == gastMap[ucLable_X][ucLable_Y].ucNeighborNum
&& 1 == gastMap[ucLable_X][ucLable_Y].ucValue)
{
ucOneWayNodeNum++;
}
}
}
gucTraceNodeNumber = gucTraceNodeNumber+1-ucOneWayNodeNum;
printf("%d\n",gucTraceNodeNumber);
return;
}
void main()
{
INT8 cResult = FAIL;

gucTraceNodeNumber = 0;
guiiterative = 0;
memset(&gstStep,0,sizeof(TRACE_STRUCT));
memset(&gstStep_max,0,sizeof(TRACE_STRUCT));

Init_Trace_Node();

Init_Node_Neighbor();

print_map();

Delete_Isolated_Point();
cResult = Get_Next_Step(START_X,START_Y);

print_step(&gstStep_max);
printf("OK!\nnumber of iterative is:%d\r",guiiterative);
printf("\n");

getchar();

return;
}

void Get_Return_Location()
{
UINT8 ucLable_X = 0;
UINT8 ucLable_Y = 0;
UINT8 ucloop = 0;
UINT8 ucloop1 = 0;
UINT8 ucMax_Step = 0;
NODE_STRUCT *pstNode = NULL;
UINT8 ucNotVisitedNeighborNum=0;
UINT8 ucNotVisitedNeighbor_Lable_X=0;
UINT8 ucNotVisitedNeighbor_Lable_Y=0;
UINT8 ucMax_Step_Lable_X=0;
UINT8 ucMax_Step_Lable_Y=0;

gstReturnLoction.ucLable_X = MAX_MAP_SIZE_X;
gstReturnLoction.ucLable_Y = MAX_MAP_SIZE_Y;

if(gstStep.ucStepNum < 2)
{
return;
}

ucMax_Step_Lable_X = gstStep_max.astStep[gstStep.ucStepNum-1].ucLable_X;
ucMax_Step_Lable_Y = gstStep_max.astStep[gstStep.ucStepNum-1].ucLable_Y;

if (gastMap[ucMax_Step_Lable_X][ucMax_Step_Lable_Y].ucNeighborNum > 1)
{

for(ucloop = gstStep.ucStepNum-2; ucloop >= 0;ucloop--)
{
ucLable_X = gstStep.astStep[ucloop].ucLable_X;
ucLable_Y = gstStep.astStep[ucloop].ucLable_Y;
ucNotVisitedNeighborNum = 0;
for(ucloop1 = 0; ucloop1 < gastMap[ucLable_X][ucLable_Y].ucNeighborNum;ucloop1++)
{
pstNode = gastMap[ucLable_X][ucLable_Y].apNeighbor[ucloop1];
if (FALSE == pstNode->bVisited && 1 == pstNode->ucValue )
{
ucNotVisitedNeighborNum++;
ucNotVisitedNeighbor_Lable_X = pstNode->ucLable_X;
ucNotVisitedNeighbor_Lable_Y = pstNode->ucLable_Y;
}
}

if (ucNotVisitedNeighborNum > 0)
{
gstReturnLoction.ucLable_X = ucLable_X;
gstReturnLoction.ucLable_Y = ucLable_Y;
if ( ucNotVisitedNeighborNum == 1 && ucloop>0 )
{
ucLable_X = gstStep.astStep[ucloop-1].ucLable_X;
ucLable_Y = gstStep.astStep[ucloop-1].ucLable_Y;
for(ucloop1 = 0; ucloop1 < gastMap[ucLable_X][ucLable_Y].ucNeighborNum;ucloop1++)
{
pstNode = gastMap[ucLable_X][ucLable_Y].apNeighbor[ucloop1];
if (FALSE == pstNode->bVisited && 1 == pstNode->ucValue)
{
if (ucNotVisitedNeighbor_Lable_X == pstNode->ucLable_X
&&ucNotVisitedNeighbor_Lable_Y == pstNode->ucLable_Y)
{
gstReturnLoction.ucLable_X = ucLable_X;
gstReturnLoction.ucLable_Y = ucLable_Y;
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
}
}
}
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
if (ucloop == 0)
{
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
}
}
else /*(gastMap[ucMax_Step_Lable_X][ucMax_Step_Lable_Y].ucNeighborNum == 1)*/
{

for(ucloop = gstStep.ucStepNum-2; ucloop >= 0;ucloop--)
{
ucLable_X = gstStep.astStep[ucloop].ucLable_X;
ucLable_Y = gstStep.astStep[ucloop].ucLable_Y;
ucNotVisitedNeighborNum = 0;
for(ucloop1 = 0; ucloop1 < gastMap[ucLable_X][ucLable_Y].ucNeighborNum;ucloop1++)
{
pstNode = gastMap[ucLable_X][ucLable_Y].apNeighbor[ucloop1];
if (FALSE == pstNode->bVisited && 1 == pstNode->ucValue && 1 < pstNode->ucNeighborNum)
{
ucNotVisitedNeighborNum++;
ucNotVisitedNeighbor_Lable_X = pstNode->ucLable_X;
ucNotVisitedNeighbor_Lable_Y = pstNode->ucLable_Y;
}
}

if (ucNotVisitedNeighborNum > 0)
{
gstReturnLoction.ucLable_X = ucLable_X;
gstReturnLoction.ucLable_Y = ucLable_Y;
if ( ucNotVisitedNeighborNum == 1 && ucloop>0 )
{/*只有1个*/
ucLable_X = gstStep.astStep[ucloop-1].ucLable_X;
ucLable_Y = gstStep.astStep[ucloop-1].ucLable_Y;
for(ucloop1 = 0; ucloop1 < gastMap[ucLable_X][ucLable_Y].ucNeighborNum;ucloop1++)
{
pstNode = gastMap[ucLable_X][ucLable_Y].apNeighbor[ucloop1];
if (FALSE == pstNode->bVisited && 1 == pstNode->ucValue && 1 < pstNode->ucNeighborNum)
{
if (ucNotVisitedNeighbor_Lable_X == pstNode->ucLable_X
&&ucNotVisitedNeighbor_Lable_Y == pstNode->ucLable_Y)
{
gstReturnLoction.ucLable_X = ucLable_X;
gstReturnLoction.ucLable_Y = ucLable_Y;
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
}
}
}
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
if (ucloop == 0)
{
if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}
}
}

if ( MAX_MAP_SIZE_X == gstReturnLoction.ucLable_X
||MAX_MAP_SIZE_Y == gstReturnLoction.ucLable_Y )
{
print_step(&gstStep);
}
return;
}

这个也太强了,有点晕,

没看到强，看到了没有注释，没人会替你优化的，自己来吧


毛主席说过：自己动手丰衣足食啊！