方法：深搜

思路：

遍歷島嶼的每個節點，每個節點都查找它的四個方向，當觸碰到邊界（邊界是水），或者格子是水的時候，邊長加一。

題目說只有一個島嶼，所以深搜一次就完成了。

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);}}
}