baidu第2题
寻找迷宫一条出路，'o'等于通路，'x'等于障碍，如图1。请给出走出迷宫的算法描述和代码，输出结果图2所示结果
（要求：通过“>”“V”“<”“^”表示路线及方向)
图1：
x x x x x x x x
o o o o o x x x
x o x x x x x x
x o x x x x x x
x o x x x x x x
x o x x o o o x
x o o o o x o o
x x x x x x x x
图2：
x x x x x x x x
> v o o o x x x
x v x x x x x x
x v x x x x x x
x v x x x x x x
x v x x > > v x
x v > > ^ x > >
x x x x x x x x
请补全void findpath(int x, int y)部分的代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 8

 
int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};
char A[4] = {'v', '<', '^', '>'};
char maze[MAX_SIZE][MAX_SIZE] =
        {{'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'},
         {'o', 'o', 'o', 'o', 'o', 'x', 'x', 'x'},
         {'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
         {'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
         {'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
         {'x', 'o', 'x', 'x', 'o', 'o', 'o', 'x'},
         {'x', 'o', 'o', 'o', 'o', 'x', 'o', 'o'},
         {'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}};

 
void findpath(int x, int y)
{
         //请补充该部分代码
}
int main()
{
        findpath(1, 0);
}

解法一：使用非递归

#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <iostream>
#define MAX_SIZE 8

using namespace std;

struct dir 
{
    int x, y;
    int d;
};

int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};
char A[4] = {'<', 'V', '>', '^'};
char maze[MAX_SIZE][MAX_SIZE] =
{
{'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'},
{'o', 'o', 'o', 'o', 'o', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'o', 'o', 'o', 'x'},
{'x', 'o', 'o', 'o', 'o', 'x', 'o', 'o'},
{'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}
};

void print()
{
    int i, j;
    for (i = 0; i < MAX_SIZE; i++)
    {
        for (j = 0; j < MAX_SIZE; j++)
            cout<<maze[i][j]<<' ';
        cout<<"\n";
    }
}

void findpath(int x, int y)
{
    
    //请补充该部分代码
    int mark[MAX_SIZE][MAX_SIZE]={0};
    stack<struct dir> st;
    int i, j, d;
    int g, h;
    struct dir tmp;
    tmp.x = x; tmp.y = y;tmp.d = 0;
    st.push(tmp);
    while (st.empty() == false)
    {
        tmp = st.top();
        st.pop();
        i = tmp.x; j = tmp.y; d = tmp.d; 
        while (d < 4)
        {
            g = i + H[d]; h = j + V[d];
            if (maze[g][h] == 'o' && mark[g][h] == 0)
            {
                mark[g][h] = 1;
                maze[i][j] = A[d];
                tmp.x = i; tmp.y = j; tmp.d = d;
                st.push(tmp);
                i = g; j = h; d = 0;
            }
            else
                d++;
            if (i == 6 && j == 7)
            {
                cout<<"find path \n";
                print();
                return;
            }
        }

    }
    cout << "no path!\n";
}
int main()
{
    findpath(1, 0);
    return 0;
}

递归实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 8

int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};
//char A[4] = {'<', 'V', '>', '^'};
char A[4] = {'v', '<', '^', '>'};
char maze[MAX_SIZE][MAX_SIZE] =
{
{'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'},
{'o', 'o', 'o', 'o', 'o', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'x', 'x', 'x', 'x'},
{'x', 'o', 'x', 'x', 'o', 'o', 'o', 'x'},
{'x', 'o', 'o', 'o', 'o', 'x', 'o', 'o'},
{'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}
};


void findpath(int x, int y)
{
    
    //请补充该部分代码
    int i,j,k;
    
    if ( x == 6 && y == 7 )
    {
        maze[x][y] = A[3];
        for ( k = 0; k < MAX_SIZE; k++ )
        {
            for( j = 0; j < MAX_SIZE; j++ )
            {
                printf ( "%c ", maze[k][j] );
            }
            printf("\n");
            
        }
        exit(0);
    }
    
    for (i = 0; i < 4; i++ )
    {
        if ( (x + V[i] >= 0)&& (x+V[i] < MAX_SIZE )&&(y+H[i] >= 0)&&(y+H[i] < MAX_SIZE )&& maze[x+V[i]][y+H[i]] == 'o' )
        {
            maze[x][y] = A[(i+2)%4];
            findpath(x+V[i],y+H[i]);
            maze[x][y] = 'o';
        }
    }
    return;
}
int main()
{
    findpath(1, 0);
    return 0;
}

好强呀，是哪个公司的笔试题，这么变态。

顶起

10fen

顶.......

   本人只是简单的复制黏贴然后看下运行结果，不求甚解。。。。。。。。

最基本的啊！ 别把数据结构和算法还给老师了