八连通岛屿计数
2026-10-25 · 来自《算法讲解058-必备-洪水填充》 · 手机上只能看题，答题回电脑
给定 n 行 m 列的网格，'1' 表示陆地，'0' 表示水。若两个陆地格子在八个方向（上下左右及四个斜对角）中任一方向相邻，则视为连通。求连通块（岛屿）数量。
输入：第一行 n m（1≤n,m≤1000，n·m≤10^6）；接下来 n 行，每行一个长度为 m 的 01 字符串。
输出：一个整数，岛屿数量。
样例输入：
2 3
101
010
样例输出：
1
说明：三个 '1' 通过斜对角两两相连，属于同一片岛。
提示：方向从 4 个扩展到 8 个，注意不要重复访问 · 斜对角相邻也算连通，样例中 (0,0) 与 (1,1) 相连
你上次 95 分
思路完全正确：四连通 flood fill 累加权值，显式栈避免 1e6 规模递归爆栈，long long 防溢出，复杂度 O(nm) 达标。边界也考虑到了无陆地输出 0（ans 初值 0 即可）。唯一小瑕疵：没有明确提到读入时 01 字符串与权值矩阵的对应关系（权值矩阵是 n 行 m 个整数，需按行列对齐），以及 w 为 0 的格子只出现在水格、陆地权值恒正，不影响累加；另外可提一句用一维数组/坐标压平来省内存，但 O(nm) visited 在 1e6 下完全可接受。整体是可直接落地的正确方案。