#include<stdio.h>
#include<stdlib.h>
#define m 4//行
#define n 4//列
struct xy
{
int x;
int y;
};
typedef struct stack
{
struct xy coordinate;
struct stack* next;
}stack;
void init(stack* p)
{
p->next = NULL;
}
void push(stack* p,struct xy cdnt)
{
stack* temp = p;
while(temp->next != NULL)
temp = temp->next;
stack* newValue = (stack*)malloc(sizeof(struct stack)*1);
newValue->coordinate = cdnt;
newValue->next = temp->next;
temp->next = newValue;
}
void pop(stack* p)
{
stack* tempp = p;
stack* temp = p->next;
while(temp->next != NULL)
temp = temp->next,tempp = tempp->next;
tempp->next = NULL;
free(temp);
}
void browse(stack* p)
{
stack* temp = p->next;
while(temp != NULL)
printf("(%d,%d)\n",temp->coordinate.y,temp->coordinate.x),temp = temp->next;
}
struct xy getEnd(struct stack* p)
{
stack* temp = p;
while(temp->next != NULL)
temp = temp->next;
return temp->coordinate;
}
int getSize(stack* p)
{
int size = 0;
stack* temp = p->next;
while(temp != NULL)
{
size++;
temp = temp->next;
}
return size;
}
int main()
{
int path[m+1][n+1] = {0};
int col = 0,row = 0;
int i = 0,j = 0;
int temp_col = 0,temp_row = 0,t_col = 0,t_row = 0;
int flag = 0;
struct xy t_pair;
//stack A,B;
stack* Ahead = (stack*)malloc(sizeof(struct stack)*1);
stack* Bhead = (stack*)malloc(sizeof(struct stack)*1);
init(Ahead); init(Bhead);
for(;i<m;i++)
for(j=0;j<n;j++)
{
printf("input 0 or 1\n");
scanf("%d",&path[i][j]);
}
i = j = 0;
if(path[0][0] == 0 || path[m-1][n-1] == 0)
{
printf("There is no way\n");
return 1;
}
while(1)
{
//检验是否已经到达末尾
if(col == n-1 && row == m-1 && path[row][col] == 1)
{
//到达尾端，意味着找到一条路
flag = 1;
printf("Find a way,it's\n");
browse(Ahead);
printf("(%d,%d)\n",m-1,n-1);
if(getSize(Bhead) != 0)
{
temp_col = getEnd(Bhead).x;
temp_row = getEnd(Bhead).y;
while(1)
if(getEnd(Ahead).x == temp_col && getEnd(Ahead).y == temp_row)
break;
else
pop(Ahead);
col = temp_col + 1;
row = temp_row;
pop(Bhead);
}
else
return 1;
}
else//还没有到末尾的情况
{
if(path[row + 1][col] == 1 && path[row][col + 1] == 1)
{
t_pair.x = col;t_pair.y = row;
push(Ahead,t_pair);
push(Bhead,t_pair);
row++;
continue;
}
//下面不是右边也不是
if(path[row + 1][col] == 0 && path[row][col + 1] == 0)
{
if(getSize(Bhead))
{
//vector::iterator iter = B.end() - 1;
col = getEnd(Bhead).x + 1;row = getEnd(Bhead).y;//回到上一次分叉处，搜索右侧路径
pop(Ahead);
pop(Bhead);
continue;
}
else
return 1;
}
//下面是，右边不是
if(path[row + 1][col] == 1 && path[row][col + 1] == 0)
{
t_pair.x = col;t_pair.y = row;
push(Ahead,t_pair);
row++;
continue;
}
//下面不是，右边是
if(path[row + 1][col] == 0 && path[row][col + 1] == 1)
{
t_pair.x = col;t_pair.y = row;
push(Ahead,t_pair);
col++;
continue;
}
}
}
if(!flag)
printf("There is no way\n");
return 0;
}
|
