方法：深搜

思路：

遍历岛屿的每个节点，每个节点都查找它的四个方向，当触碰到边界（边界是水），或者格子是水的时候，边长加一。

题目说只有一个岛屿，所以深搜一次就完成了。

import java.util.*;public class Main {// 方向标private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 计数器private static int count = 0;// 深搜private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {if (visited[x][y]) {return;}visited[x][y] = true;// 处理本节点，当触碰到边界（边界是水），或者格子是水的时候，边长加一// 上if (x - 1 < 0 || grid[x - 1][y] == 0) {count++;}// 下if (x + 1 >= grid.length || grid[x + 1][y] == 0) {count++;}// 左if (y - 1 < 0 || grid[x][y - 1] == 0) {count++;}// 右if (y + 1 >= grid[0].length || grid[x][y + 1] == 0) {count++;}// 四个方向for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (grid[nextX][nextY] == 1) {dfs(grid, visited, nextX, nextY);}}}public static void main(String[] args) {// 录入数据Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] grid = new int[n][m];boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = in.nextInt();}}// 遍历矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {// 题目说只有一个岛屿，深搜一次就搞定了dfs(grid, visited, i, j);break;}}}System.out.println(count);}
}

方法：数学

思路：

1. 先求岛屿总数sum，如果每一个都是孤岛，总边数 = sum*4
2. 再求重叠的孤岛，每重叠一条边，边数减二。重叠cover条，就是减去2*cover
3. 注意，要避免重复计算。顺序遍历的话，只算左和上就好，不要算右和下。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = in.nextInt();}}int sum = 0;    // 陆地数量int cover = 0;  // 相邻数量for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {sum++; // 统计总的陆地数量// 统计上边相邻陆地if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;// 统计左边相邻陆地if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;// 为什么没统计下边和右边？ 因为避免重复计算}}}System.out.println(sum * 4 - cover * 2);}
}

方法：广搜

思路：

在无权图中，用广搜求最短路最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

枚举，用26个字母替换当前字符串的每一个字符，在看替换后是否在 wordSet里出现过，就可以判断两个字符串是否是链接的。

使用visitMap，记录已访问的字符串及其路径长度。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();String beginStr = in.next();String endStr = in.next();// word集Set<String> wordSet = new HashSet<>();for (int i = 0; i < n; i++) {wordSet.add(in.next());}// 记录已访问的字符串及其路径长度Map<String, Integer> visitMap = new HashMap<>();// 初始化队列Deque<String> que = new ArrayDeque<>();que.offer(beginStr);// 初始化访问映射visitMap.put(beginStr, 1);while (!que.isEmpty()) {String word = que.poll();int path = visitMap.get(word);// 逐个字符替换尝试for (int i = 0; i < word.length(); i++) {// 转换为字符数组便于修改char[] charArray = word.toCharArray();// 尝试26个字母for (char c = 'a'; c <= 'z'; c++) {charArray[i] = c;String newWord = new String(charArray);// 找到目标单词if (newWord.equals(endStr)) {System.out.println(path + 1);return;}// 检查是否在集合中且未被访问过if (wordSet.contains(newWord) && !visitMap.containsKey(newWord)) {visitMap.put(newWord, path + 1);que.offer(newWord);}}}}// 无法到达目标单词System.out.println(0);}
}

方法：广搜

思路：

可以说是广搜模板题了。录入数据之后，用visited数组做访问标志，广搜就完成了。

import java.util.*;public class Main {// 邻接表private static List<List<Integer>> graph = new ArrayList<>();// 访问标志private static boolean[] visited;// 广搜private static void bfs(int start) {Deque<Integer> que = new ArrayDeque<>();visited[start] = true;que.offer(start);while (!que.isEmpty()) {int node = que.poll();for (int i : graph.get(node)) {if (!visited[i]) {visited[i] = true;que.offer(i);}}}}// 主函数public static void main(String[] args) {// 录入数据Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();visited = new boolean[n + 1];for (int i = 0; i <= n; i++) {graph.add(new LinkedList<>());}for (int i = 0; i < k; i++) {int from = in.nextInt();int to = in.nextInt();graph.get(from).add(to);}// 广搜bfs(1);// 检查输出boolean flag = true;for (int i = 1; i <= n; i++) {if (!visited[i]) {flag = false;break;}}if (flag) {System.out.println(1);} else {System.out.println(-1);}}
}