走迷宫P1238（深度优先搜索）
本帖最后由 KaQqi 于 2019-4-8 19:24 编辑#include <stdio.h>
char start;
char end;
int m,n;
int is_result = -1;
class Position
{
public:
char is_available;
};
Position buffer;
class Route
{
public:
char horizontal;
char vertical;
};
Route position_buffer;//用来记录路线
int count = 0;
void input()
{
scanf("%d %d",&m,&n);
for(int i = 1;i<=m;i++)//input
{
for(int j = 1;j<=n;j++)
{
scanf("%d",&buffer.is_available);
}
}
scanf("%d %d",&start,&start);
scanf("%d %d",&end,&end);
}
void Output()
{
for(int i=1;i<count;i++)
{
printf("(%d,%d)->",position_buffer.horizontal,position_buffer.vertical);
}
printf("(%d,%d)\n",end,end);
}
int CheckRepeat(int horizontal,int vertical)//没有重复为通过返回1
{
for(int i = 1;i<=count;i++)
{
if(position_buffer.horizontal == horizontal && position_buffer.vertical == vertical)
{
return 0;
}
}
return 1;
}
int Go(int horizontal,int vertical)//当前横纵坐标
{
count ++;
position_buffer.horizontal = horizontal;
position_buffer.vertical = vertical;
if(horizontal == end && vertical == end)
{
position_buffer.horizontal = 0;
position_buffer.vertical = 0;
Output();
count --;
is_result = 0;
return 0;
}
for(int i = 1;i<=4;i++)//i为1横着走,i为2竖着走
{
if(i == 4&&buffer.is_available == 1&&CheckRepeat(horizontal+1,vertical))//向下
{
Go(horizontal+1,vertical);
}
if(i == 3&&buffer.is_available == 1&&CheckRepeat(horizontal,vertical+1))//向右
{
Go(horizontal,vertical+1);
}
if(i==2&&buffer.is_available == 1&&CheckRepeat(horizontal-1,vertical))//向上
{
Go(horizontal-1,vertical);
}
if(i == 1&&buffer.is_available == 1&&CheckRepeat(horizontal,vertical-1))//向左
{
Go(horizontal,vertical-1);
}
}
count --;
}
int main()
{
input();
Go(start,start);
if(is_result == -1)
{
printf("-1");
}
return 0;
}
//by KaQqi 20190407
页:
[1]