网站建设在哪学,做非法网站判什么邢,海南网站建设方案,做网站就业要会什么问题题目
给定一个 m x n 的整数矩阵 mat#xff0c;我们需要找出从某个单元格出发可以访问的最大单元格数量。移动规则是可以从当前单元格移动到同一行或同一列的任何其他单元格#xff0c;但目标单元格的值必须严格大于当前单元格的值。需要返回最大可访问的单元格数量。
示例…题目
给定一个 m x n 的整数矩阵 mat我们需要找出从某个单元格出发可以访问的最大单元格数量。移动规则是可以从当前单元格移动到同一行或同一列的任何其他单元格但目标单元格的值必须严格大于当前单元格的值。需要返回最大可访问的单元格数量。
示例
示例 1 输入mat [[3,1],[3,4]]
输出2
解释从第 1 行、第 2 列的单元格开始可以访问 2 个单元格。
示例 2 输入mat [[1,1],[1,1]]
输出1
解释由于目标单元格必须严格大于当前单元格只能访问 1 个单元格。
示例 3 输入mat [[3,1,6],[-9,5,7]]
输出4
解释从第 2 行、第 1 列的单元格开始可以访问 4 个单元格。
提示
m mat.lengthn mat[i].length1 m, n 10^51 m * n 10^5-10^5 mat[i][j] 10^5
解决方案
采用深度优先搜索DFS结合动态规划DP来解决此问题。用 dp[i][j] 表示从位置 (i, j) 出发可以访问的最大单元格数。
代码
#include stdbool.h
#include stdlib.h
#include stdio.h#define MAX(a,b) ((a) (b) ? (a) : (b))int matSize, matColSize;
int **mat, **dp;bool isValid(int x, int y) {return x 0 x matSize y 0 y matColSize;
}int dfs(int x, int y) {if (dp[x][y] ! 0) return dp[x][y];int maxLen 1;for (int col 0; col matColSize; col) {if (col ! y mat[x][col] mat[x][y]) {maxLen MAX(maxLen, 1 dfs(x, col));}}for (int row 0; row matSize; row) {if (row ! x mat[row][y] mat[x][y]) {maxLen MAX(maxLen, 1 dfs(row, y));}}dp[x][y] maxLen;return maxLen;
}int maxIncreasingCells(int** matrix, int matrixSize, int* matrixColSize){mat matrix;matSize matrixSize;matColSize *matrixColSize;dp (int**)calloc(matSize, sizeof(int*));for (int i 0; i matSize; i) {dp[i] (int*)calloc(matColSize, sizeof(int));}int maxCells 0;for (int i 0; i matSize; i) {for (int j 0; j matColSize; j) {maxCells MAX(maxCells, dfs(i, j));}}for (int i 0; i matSize; i) {free(dp[i]);}free(dp);return maxCells;
}
实现步骤
1. 初始化和输入处理
读取输入矩阵并初始化 dp 数组。dp[i][j] 用于存储从位置 (i, j) 出发可以访问的最大单元格数。
int matSize, matColSize;
int **mat, **dp;dp (int**)calloc(matSize, sizeof(int*));
for (int i 0; i matSize; i) {dp[i] (int*)calloc(matColSize, sizeof(int));
}2. 定义有效移动检查函数
检查从当前单元格移动到目标单元格是否合法即目标单元格的值必须严格大于当前单元格的值。
bool isValid(int x, int y) {return x 0 x matSize y 0 y matColSize;
}3. 深度优先搜索DFS
若 dp[x][y] 已计算直接返回。遍历同一行和同一列中的单元格若满足条件递归计算并更新 dp[x][y]。
int dfs(int x, int y) {if (dp[x][y] ! 0) return dp[x][y];int maxLen 1;// 遍历同一行中的其他单元格for (int col 0; col matColSize; col) {if (col ! y mat[x][col] mat[x][y]) {maxLen MAX(maxLen, 1 dfs(x, col));}}// 遍历同一列中的其他单元格for (int row 0; row matSize; row) {if (row ! x mat[row][y] mat[x][y]) {maxLen MAX(maxLen, 1 dfs(row, y));}}dp[x][y] maxLen;return maxLen;
}4. 主逻辑
遍历矩阵每个单元格计算从每个单元格出发可以访问的最大单元格数。更新并返回全局最大值。
int maxIncreasingCells(int** matrix, int matrixSize, int* matrixColSize){mat matrix;matSize matrixSize;matColSize *matrixColSize;dp (int**)calloc(matSize, sizeof(int*));for (int i 0; i matSize; i) {dp[i] (int*)calloc(matColSize, sizeof(int));}int maxCells 0;// 遍历每个单元格for (int i 0; i matSize; i) {for (int j 0; j matColSize; j) {maxCells MAX(maxCells, dfs(i, j));}}for (int i 0; i matSize; i) {free(dp[i]);}free(dp);return maxCells;
}复杂度分析
时间复杂度O(m * n)每个单元格只被访问一次。空间复杂度O(m * n)用于存储 dp 数组。
结果
我尽力了。。。不愧是困难提题目
贴一个优化前的代码
#include stdbool.h
#include stdlib.h
#include stdio.h
#define MAX(a,b) ((a) (b) ? (a) : (b))
int gotoNext(int** dp, int matSize, int* matColSize, int** mat, int beginCol, int beginRow, int* tmpStepCnt, bool** isVisited)
{if(dp[beginCol][beginRow] ! 0){(*tmpStepCnt) dp[beginCol][beginRow];return (*tmpStepCnt);}(*tmpStepCnt);isVisited[beginCol][beginRow] true;int tmp_left 0, tmp_right 0, tmp_up 0, tmp_down 0;int left 0, right 0, up 0, down 0;int cnt 0;for (int i 1; i matSize; i){if(beginCol i matSize - 1 !isVisited[beginCol i][beginRow] mat[beginCol i][beginRow] mat[beginCol][beginRow]) {tmp_right gotoNext(dp, matSize, matColSize, mat, beginCol i, beginRow, cnt, isVisited);right MAX(tmp_right, right);cnt 0;// printf(right %d\n,right);}else{// // printf(cant goto [%d][%d]\n,beginCol i, beginRow);}if(beginCol - i 0 !isVisited[beginCol - i][beginRow] mat[beginCol - i][beginRow] mat[beginCol][beginRow]) {tmp_left gotoNext(dp, matSize, matColSize, mat, beginCol - i, beginRow, cnt, isVisited);left MAX(tmp_left, left);cnt 0;// printf(left %d\n,left);}else{// // printf(cant goto [%d][%d]\n,beginCol - i, beginRow);}}for (int i 1; i (*matColSize); i){if(beginRow i (*matColSize) - 1 !isVisited[beginCol][beginRow i] mat[beginCol][beginRow i] mat[beginCol][beginRow]) {tmp_down gotoNext(dp, matSize, matColSize, mat, beginCol, beginRow i, cnt, isVisited);down MAX(tmp_down, down);cnt 0;// printf(down %d\n,down);}else{// // printf(cant goto [%d][%d]\n,beginCol, beginRow i);}if(beginRow - i 0 !isVisited[beginCol][beginRow - i] mat[beginCol][beginRow - i] mat[beginCol][beginRow]){tmp_up gotoNext(dp, matSize, matColSize, mat, beginCol, beginRow - i, cnt, isVisited);up MAX(tmp_up, up);cnt 0;// printf(up %d\n,up);}else{// // printf(cant goto [%d][%d]\n,i, beginRow - i);}}isVisited[beginCol][beginRow] false;(*tmpStepCnt) MAX(MAX(left, right), MAX(up, down));return (*tmpStepCnt);
}int maxIncreasingCells(int** mat, int matSize, int* matColSize){int stepCnt 0;int **dp (int**)calloc(matSize, sizeof(int*)); // 记录从某个格子开始走可以走多少个格子。bool **isVisited (bool**)calloc(matSize, sizeof(bool*)); // 记录某个格子是否被访问防止死循环。for (int i 0; i matSize; i){dp[i] (int*)calloc((*matColSize), sizeof(int)); // 记录从某个格子开始走可以走多少个格子。isVisited[i] (bool*)calloc((*matColSize), sizeof(bool)); // 记录某个格子是否被访问防止死循环。}for (int i 0; i matSize; i){for (int j 0; j (*matColSize); j){int tmpStepCnt 0;tmpStepCnt gotoNext(dp, matSize, matColSize, mat, i, j, tmpStepCnt, isVisited);stepCnt MAX(tmpStepCnt, stepCnt);dp[i][j] tmpStepCnt;// printf(dp[%d][%d] %d\n, i,j,dp[i][j]);}}return stepCnt;
}这个更惨
