矩阵中的路径

非递归深度搜索

    bool hasPath(char* matrix, int rows, int cols, char* str)
    {  
        stack<pair<pair<int, int>, int> > s;
        int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  //右下左上
        int tx, ty, n, m;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
            {
                vector<vector<int> > visited(rows,vector<int>(cols, 0));
                if(matrix[i * cols + j] == str[0])
                {
                    pair<int, int> p(i, j);
                    pair<pair<int, int >, int> q(p, 0);
                    s.push(q);
                    while(!s.empty())
                    {   
                        n = s.top().first.first;
                        m = s.top().first.second;
                        if(s.top().second == (strlen(str) - 1))
                            return true;
                        visited[n][m] = 1;
                        int valid = s.top().second;
                        s.pop();
                        for(int k = 0; k < 4; k++)
                        {
                            tx = n + next[k][0];
                            ty = m + next[k][1];
                            if(tx >= 0 && tx < rows && ty >= 0 && ty < cols && 
                            visited[tx][ty] != 1 &&
                            matrix[tx * cols + ty] == str[valid + 1])
                            {
                                pair<int, int> p(tx, ty);
                                pair<pair<int, int >, int> q(p, valid + 1);
                                s.push(q);
                            }
                        }
                        if(!s.empty() && s.top().second == (strlen(str) - 1))
                            return true;
                    }
                }
            }
        return false;
    }