题解 | #通配符匹配# 拓扑排序

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int dis[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    bool chk(vector<vector<int> >& matrix,int row,int col){
        for(int i=0;i<4;i++){
            int r = row + dis[i][0],c = col + dis[i][1];
            if(0<=r && r<matrix.size() && 0<=c && c < matrix[0].size()){
                if(matrix[r][c] < matrix[row][col]) return false;
            }
        }
        return true;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        if(matrix.empty())return 0;
        int row = matrix.size(),col = matrix[0].size();
        int res = 0;
        queue<pair<int,int>> rec;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(chk(matrix,i,j)) rec.push({i,j});
            }
        }
        while(!rec.empty()){
            int k = rec.size();
            while(k-->0){
                pair<int,int> t = rec.front();
                rec.pop();
                int ro = t.first,co = t.second;
                if(matrix[ro][co] == 1001){
                    continue;//当前ro co已经被另外路径处理过
                }
                matrix[ro][co] = 1001;
                for(int i=0;i<4;i++){
                    int r = ro + dis[i][0],c = co + dis[i][1];
                    if(r<0 || r>=matrix.size() || c<0 || 
                       c >= matrix[0].size() || matrix[r][c] ==1001)
                        continue;
                    if(chk(matrix,r,c)){
                        rec.push({r,c});
                    }
                }
            }
            res++;
        }
        
        return res;
    }
};