迷宫

一个迷宫，如何用DFS找出口。虽然跟大多数人的做法不一样，为了程序化，我把它复杂化了一点……

将迷宫的每一个格子用一个结构体Node表示，一个格子有上下左右四个边界。

输入邻接矩阵 -> 根据边界在第一行第一列最后一行最后一列找到入口和出口 -> 从入口开始DFS，直到找到出口为止 -> 输出路径信息。

 

#include <iostream>
using namespace std;

#define Max 1000

/*构成迷宫的基本元素:Node.*/ 
struct Node
{ 
    Node()
    {
        vis = ans = 0;
    }
    
    bool up,down,left,right;    //有墙壁则为1，无墙壁则为0
    
    bool vis;    //记录是否被访问过，用于DFS 
    
    bool ans;    //最终答案路径是否包含这个点，用于输出路径 
};

Node node[Max][Max];

int n, m;    //行数，列数 

pair<int, int> start,end;    //起点，终点坐标 

void input();
pair<int, int> findStart();
pair<int, int> findEnd(pair<int, int>);
bool dfs(pair<int, int>); 
void solve();
void print();

int main()
{        
    input();
    
    solve();

    print();
}

/*输入*/
void input()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            cin >> node[i][j].up >> node[i][j].down >> node[i][j].left >> node[i][j].right;
    }
}

void solve()
{
    start = findStart();
    
    end = findEnd(start);
    
    node[start.first][start.second].ans = 1;    //起点一定是最终路径上的点 
    
    node[end.first][end.second].ans = 1;        //终点一定是最终路径上的点 
    
    dfs(start); 
}

/*寻找起点,返回起点坐标*/ 
pair<int, int> findStart()
{
    pair<int, int> start;
    
    //扫描第一列 
    for (int i = 0; i < n; ++i)
    {
        if (node[i][0].left == 0)
        {
            start.first = i, start.second = 0;
            
            return start;
        }
    }
    //扫描最后一列 
    for (int i = 0; i < n; ++i)
    {
        if (node[i][m-1].right == 0)
        {
            start.first = i, start.second = m-1;
            
            return start;
        }
    }
    //扫描第一行 
    for (int j = 0; j < m; ++j)
    {
        if (node[0][j].up == 0)
        {
            start.first = 0, start.second = j;
                
            return start;
        }
    }
    //扫描最后一行
    for (int j = 0; j < m; ++j)
    {
        if (node[n-1][j].down == 0)
        {
            start.first = n-1, start.second = j;
                
            return start;
        }
    }
}

/*除去起点，以相同方式，寻找终点,返回终点坐标*/ 
pair<int, int> findEnd(pair<int, int> start)
{
    pair<int, int> end;
    
    //扫描第一列 
    for (int i = 0; i < n; ++i)
    {
        //无墙壁且不同于起点 
        if (node[i][0].left == 0 && (i != start.first || 0 != start.second) )
        {
            end.first = i, end.second = 0;
            
            return end;
        }
    }
    //扫描最后一列 
    for (int i = 0; i < n; ++i)
    {
        //无墙壁且不同于起点 
        if (node[i][m-1].right == 0 && (i != start.first || m-1 != start.second) )
        {
            end.first = i, end.second = m-1;
            
            return end;
        }
    }
    //扫描第一行 
    for (int j = 0; j < m; ++j)
    {
        //无墙壁且不同于起点 
        if (node[0][j].up == 0 && (j != start.second || 0 != start.first) )
        {
            end.first = 0, end.second = j;
                
            return end;
        }
    }
    //扫描最后一行
    for (int j = 0; j < m; ++j)
    {
        //无墙壁且不同于起点 
        if (node[n-1][j].down == 0 && (j != start.second || n-1 != start.first) )
        {
            end.first = n-1, end.second = j;
                
            return end;
        }
    }    
    
}

bool dfs(pair<int, int> cur)
{
    node[cur.first][cur.second].vis = 1;
    
    //找到终点 
    if (cur.first == end.first && cur.second == end.second)
        return true;
    
    /*没有墙壁，未越界，未被访问 满足三个条件就访问它*/ 
    if (node[cur.first][cur.second].up == 0 && cur.first-1 >= 0 && node[cur.first-1][cur.second].vis == 0)
    {
        if (dfs(pair<int, int>(cur.first-1, cur.second)))
        {
            node[cur.first][cur.second].ans = 1;
            
            return true;
        }
    }
    if (node[cur.first][cur.second].down == 0 && cur.first+1 < n && node[cur.first+1][cur.second].vis == 0)
    {
        if (dfs(pair<int, int>(cur.first+1, cur.second)))
        {
            node[cur.first][cur.second].ans = 1;
            
            return true;
        }
    }
    if (node[cur.first][cur.second].left == 0 && cur.second-1 >= 0 && node[cur.first][cur.second-1].vis == 0)
    {
        if (dfs(pair<int, int>(cur.first, cur.second-1)))
        {
            node[cur.first][cur.second].ans = 1;
            
            return true;
        }
    }
    if (node[cur.first][cur.second].right == 0 && cur.second+1 < m && node[cur.first][cur.second+1].vis == 0)
    {
        if (dfs(pair<int, int>(cur.first, cur.second+1)))
        {
            node[cur.first][cur.second].ans = 1;
            
            return true;
        }
    }
    
    return false;
}

void print()
{
    cout << "Start point: ";
    
    cout << start.first << ' ' << start.second << endl;
    
    cout << "End   point: ";
    
    cout << end.first << ' ' << end.second << endl;
    
    cout << "Path:\n";
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (node[i][j].ans == 1)
                cout << '*';
            else
                cout << '#';
        }
        cout << endl;
    }
    
    system("pause");
}

 

该问题本身就是一个DFS的基本问题，不算难。主要是构图方面的技巧，这种构图可能是最笨的方法，需要手动输入一大堆信息。由于时间关系，就不再优化了……