#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define ROWS 999
#define COLS 999
int length;
int wide;
typedef struct{
int map[ROWS][COLS];
int passed[ROWS][COLS];
}Maze;
typedef struct{
int x;
int y;
}point;
void init_Maze(Maze *m);
void Searchpath(Maze *m,point enter,point exit);
int Judge(int x,int y,int n,int m);
int Decision(Maze *m,point exit,int x,int y);
int main()
{ Maze *m=(Maze*)malloc(sizeof(Maze));//分配空间；
point enter,exit;
// printf("请输入迷宫\n");
init_Maze(m);//创建迷宫
//设置入口和出口。
// printf("请输入起点坐标\n");
// scanf("%d%d",&enter.x,&enter.y);
// printf("请输入终点坐标\n");
// scanf("%d%d",&exit.x,&exit.y);
enter.x=0;
enter.y=0;
exit.x=length-1;
exit.y=wide-1;
Searchpath(m,enter,exit);//寻找路径
return 0;
}
void init_Maze(Maze *m)//修建迷宫矩阵 （字符串转数组，防止将多位数识别成一位数）
{ unsigned int j;
int i=0;
char str[1024];
do{
gets(str);
if(strlen(str)==0)
{break;}
for(j=0;j<strlen(str);j++)
{ m->passed[i][j]='0'-'0'; //同时建立记录信息的数组passed
m->map[i][j]=str[j]-'0';
}
i++;
}while(1);
length=i;
wide=j;
}
void Searchpath(Maze *m,point enter,point exit)//寻找路径
{
point current;
int p;
int q=0;
char pass[1024]="";
current.x=enter.x; //入口赋值
current.y=enter.y;
m->passed[enter.x][enter.y]=1;//给记录信息的数组的起点赋1，代表经过一次，每经过一次加1
// char arr[99];
/*
1.判断是否越界；
2.选择可行的方向（是否为通路，是否越界，选择最小值）；
3.成功选择需要记录在信息数组上。
*/
do{
if(current.x==exit.x&¤t.y==exit.y)
{
break;
}
/* if(current.x==enter.x&¤t.y==enter.y)
{
if(m->passed[current.x+1][current.y]!=0&&m->passed[current.x-1][current.y]!=0&&m->passed[current.x][current.y+1]!=0&&m->passed[current.x][current.y-1]!=0)
{
printf("NO PASS");
break;
}
}
*/
p=Decision(m,exit,current.x,current.y);
//判断能否往右走(最小值)并执行以及记录行走轨迹信息
if(p==0||p==1)
{
p=0;
if(m->map[current.x][current.y+1]==0 )
{
current.y=current.y+1;
m->passed[current.x][current.y]=m->passed[current.x][current.y]+1;
//printf("R");
if(pass[q-1]!='L')
{
pass[q]='R';
q++;
}
else
q--;
continue;
}
}
//判断能否往下走
if(p==0||p==2)
{
p=0;
if(m->map[current.x+1][current.y]==0)
{
current.x=current.x+1;
m->passed[current.x][current.y]=m->passed[current.x][current.y]+1;
// printf("D");
if(pass[q-1]!='U')
{
pass[q]='D';
q++;
}
else
q--;
continue;
}
}
//判断能否往左走
if(p==0||p==3)
{
p=0;
if(m->map[current.x][current.y-1]==0)
{ current.y=current.y-1;
m->passed[current.x][current.y]=m->passed[current.x][current.y]+1;
//printf("L");
if(pass[q-1]!='R')
{
pass[q]='L';
q++;
}
else
q--;
continue;
}
}
//判断能否往上走
if(p==0||p==4)
{
p=0;
if(m->map[current.x-1][current.y]==0)
{
current.x=current.x-1;
m->passed[current.x][current.y]=m->passed[current.x][current.y]+1;
//printf("U");
if(pass[q-1]!='D')
{
pass[q]='U';
q++;
}
else
q--;
continue;
}
}
}while(1);
puts(pass);
}
//判断是否越界
int Judge(int a,int b,int m,int n)//判断移动的点是否越界；
{
if(a>=0 && a<=m)
{
if(b>=0 && b<=n)
{return 1;}
}
return 0;
}
//判断选择最小方向
int Decision(Maze *m,point exit,int x,int y)
{
int min=99;
int a=0;
int k=0;
if(Judge(x,y+1,exit.x,exit.y)==1)
{
if(m->passed[x][y+1] <min)//判断向右
{
min=m->passed[x][y+1]; //记下最小值
k=1;
}
}
if(Judge(x+1,y,exit.x,exit.y)==1)//判断向下
{
if (m->passed[x+1][y]<min)
{
min=m->passed[x+1][y];
k=2;
}
}
if(Judge(x,y-1,exit.x,exit.y)==1)
{
if(m->passed[x][y-1]<min)//判断向左
{
min=m->passed[x][y-1];
k=3;
}
}
if(Judge(x-1,y,exit.x,exit.y)==1)
{
if(m->passed[x-1][y]<min)//判断向上
{
min=m->passed[x-1][y];
k=4;
}
}
switch(k)
{
case 1: a=1;break;//右
case 2: a=2;break;//下
case 3: a=3;break;//左
case 4: a=4;break;//上
default:0;
}
return a;
}
/*
*/
