走迷宫P1238（深度优先搜索）

KaQqi

[C++] 纯文本查看 复制代码

#include <stdio.h>

char start[2];
char end[2];
int m,n;
int is_result = -1;

class Position
{
public:
        char is_available;
};

Position buffer[20][20];
class Route
{
public:
        char horizontal;
        char vertical;        
};
Route position_buffer[31];//用来记录路线 
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[i][j].is_available);
                }
        }
        scanf("%d %d",&start[1],&start[2]);
        scanf("%d %d",&end[1],&end[2]);
}

void Output()
{
        for(int i=1;i<count;i++)
        {
                printf("(%d,%d)->",position_buffer[i].horizontal,position_buffer[i].vertical);
        }
        printf("(%d,%d)\n",end[1],end[2]);
}

int CheckRepeat(int horizontal,int vertical)//没有重复为通过返回1
{
        for(int i = 1;i<=count;i++)
        {
                if(position_buffer[i].horizontal == horizontal && position_buffer[i].vertical == vertical)
                {
                        return 0;
                } 
        }
        return 1;
} 

int Go(int horizontal,int vertical)//当前横纵坐标
{
        count ++;
        position_buffer[count].horizontal = horizontal;
        position_buffer[count].vertical = vertical;
        if(horizontal == end[1] && vertical == end[2])
        {
                position_buffer[count].horizontal = 0;
                position_buffer[count].vertical = 0;
                Output();
                count --;
                is_result = 0;
                return 0;
        }
        for(int i = 1;i<=4;i++)//i为1横着走,i为2竖着走
        {
                if(i == 4&&buffer[horizontal+1][vertical].is_available == 1&&CheckRepeat(horizontal+1,vertical))//向下 
                {
                        Go(horizontal+1,vertical);
                }
                if(i == 3&&buffer[horizontal][vertical+1].is_available == 1&&CheckRepeat(horizontal,vertical+1))//向右 
                {
                        Go(horizontal,vertical+1);
                }
                if(i==2&&buffer[horizontal-1][vertical].is_available == 1&&CheckRepeat(horizontal-1,vertical))//向上 
                {
                        Go(horizontal-1,vertical); 
                }
                if(i == 1&&buffer[horizontal][vertical-1].is_available == 1&&CheckRepeat(horizontal,vertical-1))//向左 
                {
                        Go(horizontal,vertical-1);
                }
        }
        count --;
} 


int main()
{
        input();
        Go(start[1],start[2]);
        if(is_result == -1)
        {
                printf("-1");
        }
        return 0;
}

//by KaQqi 20190407