完成以下迷宮
利用二維陣列儲存每一個陣列里的值，若是不能走則為1，若是可行就是0，走過了就設為2，
一般是再復制一個陣列，用來記錄，
堆疊的思想就是將一個點的上下左右都遍歷一遍，若可行進堆疊，跳出遍歷，再尋找下一個可走的，若遇到無路可走的就退回上一步，就是出堆疊，所以就是說堆疊里記錄的是可以走到終點的路，
佇列的思想就是一直找，把所有可以走的路都走一遍，直到遇到終點，
這里的每一個可以走的點都為鏈表中的一個節點，在佇列中要記錄這個點的上一點是什么，就是哪一個點衍生出的這個點，
若是堆疊，最后在出堆疊便是所走的路徑，但是堆疊是后進先出的原理，可能為了好看最后要做些處理，
若是佇列，最后是利用找到的終點的那個節點，一直找這個節點的上一個節點，上個節點的上個節點，一直找到起點，可能為了好看最后還是要做些處理，
這里就是按照上述方法做的，但是太懶了，做出來就沒有處理了，
堆疊是比較簡單的，主要是佇列中的頭部和尾部的節點設定，和進佇列的時候是怎么回圈，這個回圈是怎么在遍歷之前的節點的也同時在加入新的節點進隊，后來我是沒有用出隊這個原理去做，
以下是用堆疊實作的
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
typedef struct stack{
int x;//記錄下標
int y;
int direction;//記錄方向
struct stack *next;
}stack;
int main(){
int maze[10][10];
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(i==0 || j==0 || i==9|| j==9){
maze[i][j]=1;
} else{
maze[i][j]=0;
}
}
}
maze[1][3]=1;
maze[1][7]=1;
maze[2][3]=1;
maze[2][7]=1;
maze[3][5]=1;
maze[3][6]=1;
maze[4][2]=1;
maze[4][3]=1;
maze[4][4]=1;
maze[5][4]=1;
maze[6][2]=1;
maze[6][6]=1;
maze[7][2]=1;
maze[7][3]=1;
maze[7][4]=1;
maze[7][6]=1;
maze[7][7]=1;
maze[8][1]=1;
//這里是輸進去的迷宮，也可以隨機實作，但是這里偷下懶
int cmaze[10][10];
for(i=0;i<10;i++){
for(j=0;j<10;j++){
cmaze[i][j]=maze[i][j];
}
}
//用一個新的二維陣列記錄走過的點
printf("\n\n");
stack *top,*p,*q,*t,*s;
top=(stack *)malloc(sizeof(stack));
top->next=NULL;
//人為設定的，(1,1)是起點，（8，8）是終點
int flag=0,x=0,y=0;
if(flag==0){
p=(stack *)malloc(sizeof(stack));
p->x=1;
p->y=1;
p->direction=-1;
q=top->next;
top->next=p;
p->next=q;
flag=1;
}
q=top->next;
x=q->x;
y=q->y;
while(q->x!=8 || q->y!=8){
//0:向左 y+1 1:向下 x+1 2:向右 y-1 3:向上 x+1
if(cmaze[x][y+1]==0){
p=(stack *)malloc(sizeof(stack));
p->x=x;
p->y=y+1;
p->direction=0;
q=top->next;
top->next=p;
p->next=q;
cmaze[x][y+1]=2;
}else if(cmaze[x+1][y]==0){
p=(stack *)malloc(sizeof(stack));
p->x=x+1;
p->y=y;
p->direction=1;
q=top->next;
top->next=p;
p->next=q;
cmaze[x+1][y]=2;
}else if(cmaze[x][y-1]==0){
p=(stack *)malloc(sizeof(stack));
p->x=x;
p->y=y-1;
p->direction=2;
q=top->next;
top->next=p;
p->next=q;
cmaze[x][y-1]=2;
}else if(cmaze[x+1][y]==0){
p=(stack *)malloc(sizeof(stack));
p->x=x;
p->y=y-1;
p->direction=3;
q=top->next;
top->next=p;
p->next=q;
cmaze[x+1][y]=2;
}else{
t=top->next;
s=t->next;
top->next=s;
free(t);
}
q=top->next;
x=q->x;
y=q->y;
//每次都是堆疊頂的元素找方向，找不到就是free掉，出堆疊，就是后退一步
}
for(i=0;i<10;i++){
for(j=0;j<10;j++){
printf(" %d",cmaze[i][j]);
}
printf("\n");
}
printf("溯源：\n");
while(top->next!=NULL){
p=top->next;
x=p->x;
y=p->y;
printf("x=%d,y=%d\n",x,y);
top=top->next;
}
return 0;
}
//佇列
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxsize 10
#define null 0
typedef struct node{
int x;
int y;
struct node*last;
struct node*next;
} lqnode;
typedef struct{
node *front,*rear;
}Queue;
//定義一個佇列的結構體，記錄頭和尾
int main(){
int maze[10][10];
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(i==0 || j==0 || i==9|| j==9){
maze[i][j]=1;
} else{
maze[i][j]=0;
}
}
}
maze[1][3]=1;
maze[1][7]=1;
maze[2][3]=1;
maze[2][7]=1;
maze[3][5]=1;
maze[3][6]=1;
maze[4][2]=1;
maze[4][3]=1;
maze[4][4]=1;
maze[5][4]=1;
maze[6][2]=1;
maze[6][6]=1;
maze[7][2]=1;
maze[7][3]=1;
maze[7][4]=1;
maze[7][6]=1;
maze[7][7]=1;
maze[8][1]=1;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
printf(" %d",maze[i][j]);
}
printf("\n");
}
Queue *q;
lqnode *p;
q=(Queue *)malloc(sizeof(Queue));
p=(lqnode *)malloc(sizeof(lqnode));
p->next=null;
q->rear=p;
q->front=p;
int x,y;
lqnode *r,*t;
r=(lqnode *)malloc(sizeof(lqnode));
r->x=1;
r->y=1;
r->last=null;
q->rear->next=r;
r->next=null;
q->rear=r;
t=q->front->next;
x=t->x;
y=t->y;
printf("可以走的點\n");
while(x!=8 || y!=8){
if(maze[x][y+1]==0){
r=(lqnode *)malloc(sizeof(lqnode));
r->x=x;
r->y=y+1;
r->last=t;
q->rear->next=r;
r->next=null;
q->rear=r;
maze[x][y+1]=2;
}
if(maze[x+1][y]==0){
r=(lqnode *)malloc(sizeof(lqnode));
r->x=x+1;
r->y=y;
r->last=t;
q->rear->next=r;
r->next=null;
q->rear=r;
maze[x+1][y]=2;
}
if(maze[x][y-1]==0){
r=(lqnode *)malloc(sizeof(lqnode));
r->x=x;
r->y=y-1;
r->last=t;
q->rear->next=r;
r->next=null;
q->rear=r;
maze[x][y-1]=2;
}
if(maze[x+1][y]==0){
r=(lqnode *)malloc(sizeof(lqnode));
r->x=x+1;
r->y=y;
r->last=t;
q->rear->next=r;
r->next=null;
q->rear=r;
maze[x+1][y]=2;
}
//可以走的就加入佇列，然后佇列是從頭開始回圈的，一邊回圈一邊加入了新元素
t=t->next;
x=t->x;
y=t->y;
printf("%d,%d\n",x,y);
}
printf("溯源：\n");
while(t->last!=NULL){
printf("x=%d,y=%d\n",t->x,t->y);
t=t->last;
}
//用last記錄每一個節點是由哪個節點走過來的
return 0;
}
1 1 1 1 是上面的迷宮，截圖沒有截好
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/518525.html
標籤：其他
上一篇：[Leetcode62]不同路徑