pta 可变大小矩阵

### PTA 全球变暖水淹岛 题解与算法分析 此问题的核心在于解决连通图中的岛屿淹没情况，涉及深度优先搜索（DFS）或广度优先搜索（BFS）。以下是详细的解答和算法设计。 #### 1. **问题描述** 给定一个二维网格地图，其中 '1' 表示陆地，'0' 表示水域。由于全球变暖的影响，某些岛屿可能被水淹没。每次洪水发生时，相邻的陆地会被视为同一片区域并一同淹没。目标是计算能够被淹没的最大岛屿数量。 #### 2. **核心思想** 该问题属于典型的连通分量问题，可以利用 DFS 或 BFS 来遍历整个地图，标记已访问过的节点，并统计独立的连通分量数目。需要注意的是，一旦某个岛屿被淹没，则不能再重复计算其面积或其他属性[^1]。 #### 3. **算法实现** 以下提供基于 Python 的 DFS 实现方案： ```python def numIslands(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': return grid[i][j] = '#' # 将当前单元格标记为已访问 directions = [(0, 1), (1, 0), (-1, 0), (0, -1)] for dx, dy in directions: ni, nj = i + dx, j + dy dfs(ni, nj) count = 0 for r in range(m): for c in range(n): if grid[r][c] == '1': # 发现有新的未访问的陆地 dfs(r, c) count += 1 # 统计一个新的岛屿 return count ``` 上述代码实现了基本的岛屿数量统计功能。对于“水淹”的扩展需求，可以在每轮洪水后重新调用 `numIslands` 函数来更新剩余岛屿的数量[^1]。 #### 4. **复杂度分析** - 时间复杂度：O(M * N)，其中 M 和 N 分别表示矩阵的高度和宽度。每个位置最多只会被访问一次。 - 空间复杂度：最坏情况下 O(M * N)，取决于递归栈的深度以及存储状态的空间开销。 #### 5. **注意事项** 需特别注意题目中提到的关键点——岛屿一旦被淹没则不可恢复。这意味着在实际编码过程中应合理管理数据结构的状态变化，防止误判或多算已经处理完毕的部分[^1]。 --- ###

### C/C++ 中数组指针与二维数组的关系 在 C 和 C++ 编程语言中，数组和指针有着紧密的联系。对于多维数组而言，理解其内存布局以及如何通过指针访问这些数据至关重要。 #### 一维数组及其指针表示法 在一维情况下，声明一个整型数组 `int arr[10];` 后，可以认为该语句创建了一个指向第一个元素地址的常量指针 `int* ptr = arr;` 或者更常见的是直接使用数组名作为指针来遍历整个数组[^1]： ```cpp for (size_t i = 0; i < sizeof(arr)/sizeof(*arr); ++i){ std::cout << *(arr+i) << ' '; } ``` #### 二维数组的基础概念 当涉及到二维或多维结构时，情况变得稍微复杂一些。考虑如下定义的一个简单的二维字符数组用于存储字符串列表: ```c char arr[N][80]; ``` 这里每一行代表一个固定长度为79个字符加终止符('\0') 的字符串缓冲区。因此，在这种特定场景下，可以通过指定索引来获取某一行的数据并将其视为单个的一维字符数组处理[^2]: ```c scanf("%s", arr[i]); // ... printf("The longest is: %s\n", tmp); ``` 但是需要注意的是，上述例子中的二维数组实际上是在连续分配的空间内按照行优先顺序排列而成的多个相同大小的一维子数组集合体；而并非真正意义上的动态可变尺寸矩阵形式存在。 #### 动态分配二维数组的方法 如果希望构建更加灵活可控的真实意义下的矩形区域，则需借助于指针实现动态内存管理功能。下面给出了一种基于堆空间申请的方式创建m×n规格化表格对象，并初始化所有单元格值均为零的例子说明[^3]: ```cpp const size_t rows = m; const size_t cols = n; double **matrix = new double*[rows]; try { for(size_t r = 0 ;r<rows;++r){ matrix[r]=new double [cols]{}; //释放资源防止泄漏 atexit([=]()mutable noexcept{ for(;r--;) delete[] matrix[r]; delete [] matrix; }); } } catch(const bad_alloc& e){ cerr<<e.what()<<'\n'; exit(EXIT_FAILURE); } // 访问第row行col列位置处的内容 auto value_at_position = matrix[row][col]; ``` 此段代码片段展示了利用双重指针(`**`)配合运算符重载机制完成对任意规模方阵实例的操作过程——先开辟若干条独立链表节点（即每行列向量），再逐一对它们内部成员赋初值直至形成完整的网格状拓扑图谱为止。 #### 使用指针对二维数组进行操作 一旦掌握了以上基础知识之后就可以尝试编写函数来进行诸如求解最大值、最小值等问题了。比如要找出给定输入序列中最长的那个单词，就需要比较各个记录项的实际占用字节数目以决定最终胜出者是谁。此时便能充分发挥指针的优势简化逻辑判断流程提高程序执行效率. 另外值得注意的地方在于：由于C风格字符串是以NULL结尾标记结束边界的特殊编码方式呈现出来的所以务必小心越界读写错误的发生以免造成不可预见的安全隐患风险。