迷宫找路

时间：2009-06-08 来源：dengjin

帮一个朋友写的小程序，是一个以数组表示的迷宫，1代表通路，0不通，要找到不同的路径。先用STL实现以下，然后写个用栈实现的c语言版本

                cin>>path[i][j];
            }
    i = j = 0;

    if(path[0][0] == 0 || path[m-1][n-1] == 0)
    {
        cout<<"迷宫没有通路\n";
        return 1;
    }
    while(1)
    {
        //检验是否已经到达末尾

        if(col == n-1 && row == m-1 && path[row][col] == 1)
        {
            //到达尾端，意味着找到一条路

            cout<<"Find a way,it's"<<endl;
            for(vector<struct xy>::iterator iter = A.begin();
             iter < A.end();iter++)
                    cout<<"("<<iter->y<<","<<iter->x<<")"<<endl;
            cout<<"("<<m-1<<","<<n-1<<")"<<endl;
            if(B.size() != 0)
            {
                vector<struct xy>::iterator iter = B.end() - 1;
                temp_col = iter->x;
                temp_row = iter->y;
                iter = A.end()-1;
                for(;iter != A.begin();iter--)
                    if(iter->x = temp_col && iter->y == temp_row)
                        break;
                    else
                        A.pop_back();
   col = temp_col + 1;
                row = temp_row;
                B.pop_back();

            }
            else
                return 1;
         }

        else//还没有到末尾的情况

        {
            if(path[row + 1][col] == 1 && path[row][col + 1] == 1)
            {
                t_pair.x = col;t_pair.y = row;
                A.push_back(t_pair);
                B.push_back(t_pair);
                row++;
                continue;
            }
            //下面不是右边也不是

            if(path[row + 1][col] == 0 && path[row][col + 1] == 0)
            {
                if(B.size())
                {
                    vector<struct xy>::iterator iter = B.end() - 1;
                    col = iter->x + 1;row = iter->y;//回到上一次分叉处，搜索右侧路径

                    A.pop_back();
                    B.pop_back();
                    continue;
                }
                else
                    return 1;
            }
            //下面是，右边不是

            if(path[row + 1][col] == 1 && path[row][col + 1] == 0)
            {
                t_pair.x = col;t_pair.y = row;
                A.push_back(t_pair);
                row++;
                continue;
            }
            //下面不是，右边是

            if(path[row + 1][col] == 0 && path[row][col + 1] == 1)
            {
                t_pair.x = col;t_pair.y = row;
                A.push_back(t_pair);
                col++;
                continue;
            }


        }
    }

    return 0;
}

c语言版本：

}

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<struct xy>::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;
}