题解 | #公共子串计算#BFS广度优先遍历

#include<iostream>
#include<vector>
#include<list>
#include<stack>

using namespace std;

typedef struct Node
{
    int x, y;
    Node* ancestor;
    Node(int _x, int _y) :ancestor(NULL), x(_x), y(_y) {}
}Node, * LPNode;

LPNode FindSibling(vector<vector<int>>& migong, int x, int y, int hang, int lie)    //这个函数是找到当前坐标的邻居有哪些
{
    LPNode p = NULL;
    if ((x - 1 >= 0) && migong[x - 1][y] != 1)
    {
        migong[x - 1][y] = 1;                                                                                          // = 1代表已经在迷宫中遍历过了
        p = new Node(x - 1, y);
    }
    else if (y + 1 < lie && migong[x][y + 1] != 1)
    {
        migong[x][y + 1] = 1;
        p = new Node(x, y + 1);
    }
    else if (x + 1 < hang && migong[x + 1][y] != 1)
    {
        migong[x + 1][y] = 1;
        p = new Node(x + 1, y);
    }
    else if (y - 1 >= 0 && migong[x][y - 1] != 1)
    {
        migong[x][y - 1] = 1;
        p = new Node(x, y - 1);
    }
    return p;
}

int main() {
    int hang , lie;
    while(cin >> hang >> lie)
    {
        if (hang == 0 && lie == 0)
        {
            cout << "(0,0)" << endl;
            return 0;
        }
        int temp;
        vector<vector<int>> migong(hang, vector<int>(lie));
        for (int i = 0; i < hang; i++)
            for (int j = 0; j < lie; j++)
            {
                cin >> temp;
                migong[i][j] = temp;
            }
        int i = 0, j = 0;
        migong[0][0] = 1;
        LPNode p = new Node(0, 0);
        list<LPNode> l;
        list<LPNode> trash;
        l.push_back(p);
        trash.push_back(p);
        LPNode next = NULL;
        do
        {
            LPNode q = l.front();
            next = FindSibling(migong, q->x, q->y, hang, lie);
            if (next)
            {
                next->ancestor = q;
                trash.push_back(next);
                l.push_back(next);
            }
            else
            {
                l.pop_front();
            }
            if ((l.back()->x == hang - 1) && (l.back()->y == lie - 1))
                break;
        } while (!l.empty());

        stack<LPNode> s;
        next = l.back();
        while (next)
        {
            s.push(next);
            next = next->ancestor;
        }

        while (!s.empty())
        {
            cout << "(" << s.top()->x << "," << s.top()->y << ")" << endl;
            s.pop();
        }
        while(!trash.empty())    //清理内存
        {
            LPNode m = trash.front();
            trash.pop_front() ;
            delete m ;
        }
        trash.clear() ;
        l.clear() ;
    }

    return 0;
}