【算法集训】基础数据结构：十一、邻接矩阵

今天题目难度比较大，后两道用的动态规划，后面再理解理解。

第一题 547. 省份数量

void dfs(int i, int n, int ret, int * color, int ** isConnected) {
    if(color[i] != -1) return ;
    color[i] = ret;
    for(int j = 0; j < n; ++j) {
        if(isConnected[i][j]) {
            dfs(j, n, ret, color, isConnected);
        }
    }
}


int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize) {
    int color[210]; //创建染色体,C的值就是元素下标
    memset(color, -1, sizeof(color));  //染色体赋初值为-1,表示未染色
    int c = 0; //要被染的下标
    int n = isConnectedSize; //数组长度(是正方形)
    for(int i = 0; i < n; ++i) {
        if(color[i] == -1) {
            ++c;  //下标代表当前着有几个"省份",
            dfs(i, n, c, color, isConnected);
        }
    }
    return c;
}

第二题 329. 矩阵中的最长递增路径

int dp[210][210]; //设置dp,元素值为当前块递增的最大长度

int dir[4][2] = {
    {-1, 0},
    {0, -1},
    {1, 0},
    {0, 1}  
};

int dfs(int x, int y, int m, int n, int** matrix) {
    int ret = 1;
    for(int i = 0; i < 4; ++i) {
        int tx = dir[i][0] + x;
        int ty = dir[i][1] + y;
        if(tx < 0 || tx >= m || ty < 0 || ty >= n) {
            continue;
        }
        if(matrix[x][y] > matrix[tx][ty]) {
            if(dp[tx][ty] == -1) {
                dp[tx][ty] = dfs(tx, ty, m, n, matrix);
            }
            if(dp[tx][ty] + 1 > ret) {
                ret = dp[tx][ty] + 1;
            }
        }
    }
    return ret;
}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    memset(dp, -1, sizeof(dp)); //设置动态数组初值
    int m = matrixSize;
    int n = matrixColSize[0];
    int ret = 0;  //记录最长的长度;
    // 遍历数组
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            //如果dp元素==-1,表明未操作过
            if(dp[i][j] == -1) {
                // 给元素赋值当前元素的最长递增长度
                dp[i][j] = dfs(i, j, m, n, matrix);
            }
            if(dp[i][j] > ret) {
                ret = dp[i][j];
            }
        }
    }
    return ret;
}