2017-03-19
#include
#include
#include
#include
#define MAX_WIDTH 30
#define MAX_HEIGHT 30
typedef struct _step
{
int x; //行坐标
int y; //列坐标
}STEP;
typedef struct _matrix
{
int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宫数据，0：表示有路，1：表示墙
int width; //矩阵（迷宫）的宽，包括最左和最有２堵墙
int height; //矩阵（迷宫）的宽，包括顶部和底部２堵墙
STEP entrance; //迷宫入口
STEP exit; //迷宫出口
}MATRIX;
MATRIX g_matrix= //初始化为一个迷宫，程序也能从文件中读入迷宫数据
{
{
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 0, 1, 0, 1, 1},
{1, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
},
7,7, //7行，7列，包括4堵墙
{1,1}, //入口坐标
{5,5} //出口坐标
};
static STEP s_shift[]=
{
{1,0}, //向右走， x++, y 不变
{0,1}, //向下走, x 不变, y++
{-1,0}, //向左走, x--, y不变
{0,-1} //向上走, x 不变, y--
};
void print_paths(STEP path[],int path_len) //打印走迷宫的路径
{
int i;
for (i=0;i
{
if (i>0)
printf("->");
printf("(%d,%d)",path[i].x, path[i].y);
}
}
void print_Matrix(MATRIX* pMatrix) //打印迷宫数据，迷宫数据包含4堵墙
{
int i,j;
for (i=0;iheight;i++)
{
for (j=0;jwidth;j++)
{
if (j!=0)
printf(" ");
printf("%d",pMatrix->data[i][j]);
}
printf("\n");
}
}
int search_path(int matric[MAX_WIDTH+2][MAX_WIDTH+2],
STEP path[],int path_len,STEP exit)
{
while (1)
{
int i,bFind;
STEP newPos;
for (bFind=0,i=0;i<4;i++) //从右，下，左，上，查找新的可以走的位置
{
newPos.x = path[path_len-1].x + s_shift[i].x;
newPos.y = path[path_len-1].y + s_shift[i].y;
if ( path_len==1 )
{
if ( g_matrix.data[newPos.x][newPos.y]==0)
{
bFind=1; break; //找到一个位置
}
}
// path[path_len-1]表示当前位置，path[path_len-2]表示上一步的位置，
// 如果新的位置等于上一个位置，将陷入循环，故要求新的位置不能是上一步的位置
else if ( (newPos.x != path[path_len-2].x || newPos.y!=path[path_len-2].y) && g_matrix.data[newPos.x][newPos.y]==0)
{
bFind=1; break; //找到一个位置
}
}
if (bFind)
{
path[path_len++]=newPos; //将新的位置追加到path数组，路径长度+1
if ( newPos.x==exit.x && newPos.y==exit.y)
return path_len;
}
else
{
matric[path[path_len-1].x][path[path_len-1].y]=1; //从当前位置，无路可走，将当前位置标记为墙
path_len--; //回退一步
if ( path_len==0)
return path_len;
}
}
}
int readMatrix(char *file)
{
char line[1024];
FILE *fp=NULL;
int i,j,x,y;
fp=fopen(file,"rt");
if (fp==NULL)
{
printf("Can not open file %s\n",file);
return 0;
}
memset(&(g_matrix),0,sizeof(g_matrix));
fgets(line,sizeof(line)-1,fp);
sscanf(line,"%d %d",&x,&y); //读入迷宫的行数和列数
if ( x>MAX_WIDTH || y>MAX_HEIGHT)
{
printf("The Matrix is too large\n");
fclose(fp);
return 0;
}
g_matrix.width=x+2; //在4条边增加4堵墙，故宽和高增加2
g_matrix.height=y+2;
for (j=0;j
{
g_matrix.data[0][j]=1; //第一行为墙
g_matrix.data[g_matrix.height-1][j]=1; //最后一行为墙
}
for (i=0;i
{
g_matrix.data[i][0]=1; //最左边的列为墙
g_matrix.data[i][g_matrix.width-1]=1; //最右边的列为墙
}
for (i=1;i
{
char *p;
fgets(line,sizeof(line)-1,fp);
j=1;
p=line;
while (1)
{
while ( *p==' ' ||*p== 9)//跳过空格符号
p++;
if ( *p>='0' && *p<='9')
{
sscanf(p,"%d",&(g_matrix.data[i][j])); //读入地i行j列的数据
while ( *p>='0' && *p<='9')
p++; //数据已经读入，跳过当前的数字
j++;
}
if (j>=g_matrix.width-2)
break;
}
}
fgets(line,sizeof(line)-1,fp);
//读入入口的行坐标和列坐标，和出口的行坐标，列坐标
sscanf(line,"%d %d %d %d",&(g_matrix.entrance.x),&(g_matrix.exit.y),&(g_matrix.exit.x),&(g_matrix.exit.y));
fclose(fp); fp=NULL;
g_matrix.entrance.x++; //增加了一列是墙，故入口横坐标+1
g_matrix.entrance.y++; //增加了一行是墙，故入口纵坐标+1
g_matrix.exit.x++; //增加了一列是墙，故入口横坐标+1
g_matrix.exit.y++; //增加了一列是墙，故入口纵坐标+1
return 1;
}
int main()
{
STEP path[MAX_WIDTH*MAX_HEIGHT];
int step_count;
if ( !readMatrix("matrix.txt") ) //不使用初始化的数据，从文件中读入迷宫数据
{
return 0; //读取失败，直接跳出
}
printf("The matrix is\n");
print_Matrix(&g_matrix);
path[0]=g_matrix.entrance; //将入口位置放入path数组
step_count = search_path(g_matrix.data,path,1,g_matrix.exit); //查找一条路径，路径的每一步的坐标放入path数组
if (step_count>0) //找到一条出路，步数>０
{
printf("\nThe path is\n");
print_paths(path,step_count);
}
else //步数<=0, 没有找到出路
printf("No solution\n");
return 0;
}
