给出一张 R 行 C 列的地图。
'#' 是陆地，'.' 是水。
上下左右相邻的陆地属于同一个岛（对角不相连）。
输出两行。
第一行输出岛的个数。
第二行输出从左上角格子走到右下角格子、只踩陆地、每次向上下左右移动一格所需的最少移动次数。
若这两个格子中有一个是水，或无法到达，输出 -1；若地图只有一格且是陆地，答案为 0。
4 5 ##..# .#... .#### #...#
3 7
2 2 #. .#
2 -1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
数岛用深度优先搜索（DFS）：从还没看过的陆地出发，把相连的陆地全部标记，就是一个岛。
最短路用广度优先搜索（BFS）：用队列从近的格子向外扩散，第一次到达时的距离就是答案——DFS 最先找到的路可能是绕远的。
DFS 用递归写很短，但深度是问题：蛇形的长岛会递归约 1,300 层，Python 默认递归上限是 1,000，会抛出 RecursionError——改用栈（list 的 append/pop）或调高 sys.setrecursionlimit。
Craykon 的递归也会在几千层停下，所以把列表当栈用（添加 和 按位置移除(数量 - 1)）。
C、C++、Java、C#、JavaScript 的默认栈放得下 2,500 层递归。
BFS 队列：Python deque，Java ArrayDeque，C# Queue<(int, int)>，C++ std::queue<std::pair<int, int>>；C、JavaScript、Craykon 每个格子只入队一次，用数组加队首下标（head）就够了。
二维标记表各语言也不同：C# new bool[r, c]（矩形数组），Java new boolean[r][c]，JavaScript 必须用 Array.from 为每行建新数组（new Array(r).fill([]) 会让每行都是同一个数组）。
Craykon 用 y * c + x 的位置存在一个列表里。
按对角连接会改变岛的个数，所以只用 4 个方向。
from collections import deque r, c = map(int, input().split())grid = [input().strip() for _ in range(r)]STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1)) def neighbors(y, x): for dy, dx in STEPS: ny, nx = y + dy, x + dx if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == "#": yield ny, nx def count_islands(): """깊이 우선 탐색(DFS)을 스택으로 — 재귀는 Python 기본 깊이 1,000을 넘을 수 있다.""" seen = [[False] * c for _ in range(r)] islands = 0 for y in range(r): for x in range(c): if grid[y][x] != "#" or seen[y][x]: continue islands += 1 seen[y][x] = True stack = [(y, x)] while stack: cy, cx = stack.pop() for ny, nx in neighbors(cy, cx): if not seen[ny][nx]: seen[ny][nx] = True stack.append((ny, nx)) return islands def shortest_path(): """너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다.""" if grid[0][0] != "#" or grid[r - 1][c - 1] != "#": return -1 dist = [[-1] * c for _ in range(r)] dist[0][0] = 0 queue = deque([(0, 0)]) while queue: y, x = queue.popleft() for ny, nx in neighbors(y, x): if dist[ny][nx] == -1: dist[ny][nx] = dist[y][x] + 1 queue.append((ny, nx)) return dist[r - 1][c - 1] print(count_islands())print(shortest_path())const lines = require("fs").readFileSync(0, "utf8").split("\n");const [r, c] = lines[0].trim().split(/\s+/).map(Number);const grid = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS = [[1, 0], [-1, 0], [0, 1], [0, -1]];const isLand = (y, x) => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] === "#"; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)function fill(seen, y, x) { seen[y][x] = true; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} function countIslands() { const seen = Array.from({ length: r }, () => new Array(c).fill(false)); let islands = 0; for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "#" && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다function shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; const dist = Array.from({ length: r }, () => new Array(c).fill(-1)); dist[0][0] = 0; const queue = [[0, 0]]; for (let head = 0; head < queue.length; head++) { const [y, x] = queue[head]; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && dist[ny][nx] === -1) { dist[ny][nx] = dist[y][x] + 1; queue.push([ny, nx]); } } } return dist[r - 1][c - 1];} console.log(countIslands());console.log(shortestPath());import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const [r, c]: number[] = lines[0].trim().split(/\s+/).map(Number);const grid: string[] = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];const isLand = (y: number, x: number): boolean => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] === "#"; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)function fill(seen: boolean[][], y: number, x: number): void { seen[y][x] = true; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} function countIslands(): number { const seen: boolean[][] = Array.from({ length: r }, () => new Array(c).fill(false)); let islands = 0; for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "#" && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다function shortestPath(): number { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; const dist: number[][] = Array.from({ length: r }, () => new Array(c).fill(-1)); dist[0][0] = 0; const queue: [number, number][] = [[0, 0]]; for (let head = 0; head < queue.length; head++) { const [y, x] = queue[head]; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && dist[ny][nx] === -1) { dist[ny][nx] = dist[y][x] + 1; queue.push([ny, nx]); } } } return dist[r - 1][c - 1];} console.log(countIslands());console.log(shortestPath());import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.StringTokenizer; public class Main { static int r, c; static String[] grid; static final int[] DY = {1, -1, 0, 0}, DX = {0, 0, 1, -1}; static boolean isLand(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y].charAt(x) == '#'; } // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) static void fill(boolean[][] seen, int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); } } static int countIslands() { boolean[][] seen = new boolean[r][c]; int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y].charAt(x) == '#' && !seen[y][x]) { islands++; fill(seen, y, x); } return islands; } // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다 static int shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; int[][] dist = new int[r][c]; for (int[] row : dist) Arrays.fill(row, -1); ArrayDeque<int[]> queue = new ArrayDeque<>(); dist[0][0] = 0; queue.addLast(new int[] {0, 0}); while (!queue.isEmpty()) { int[] cur = queue.pollFirst(); for (int d = 0; d < 4; d++) { int ny = cur[0] + DY[d], nx = cur[1] + DX[d]; if (isLand(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[cur[0]][cur[1]] + 1; queue.addLast(new int[] {ny, nx}); } } } return dist[r - 1][c - 1]; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); r = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); grid = new String[r]; for (int y = 0; y < r; y++) grid[y] = in.readLine().trim(); System.out.println(countIslands()); System.out.println(shortestPath()); }}using System;using System.Collections.Generic; class Program{ static int r, c; static string[] grid; static readonly int[] DY = { 1, -1, 0, 0 }, DX = { 0, 0, 1, -1 }; static bool IsLand(int y, int x) => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#'; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) static void Fill(bool[,] seen, int y, int x) { seen[y, x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (IsLand(ny, nx) && !seen[ny, nx]) Fill(seen, ny, nx); } } static int CountIslands() { var seen = new bool[r, c]; int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y, x]) { islands++; Fill(seen, y, x); } return islands; } // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다 static int ShortestPath() { if (!IsLand(0, 0) || !IsLand(r - 1, c - 1)) return -1; var dist = new int[r, c]; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) dist[y, x] = -1; var queue = new Queue<(int, int)>(); dist[0, 0] = 0; queue.Enqueue((0, 0)); while (queue.Count > 0) { var (y, x) = queue.Dequeue(); for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (IsLand(ny, nx) && dist[ny, nx] == -1) { dist[ny, nx] = dist[y, x] + 1; queue.Enqueue((ny, nx)); } } } return dist[r - 1, c - 1]; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); r = int.Parse(first[0]); c = int.Parse(first[1]); grid = new string[r]; for (int y = 0; y < r; y++) grid[y] = Console.ReadLine().Trim(); Console.WriteLine(CountIslands()); Console.WriteLine(ShortestPath()); }}#include <iostream>#include <queue>#include <string>#include <utility>#include <vector> int r, c;std::vector<std::string> grid;const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; bool isLand(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#'; } // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)void fill(std::vector<std::vector<bool>>& seen, int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} int countIslands() { std::vector<std::vector<bool>> seen(r, std::vector<bool>(c, false)); int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다int shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; std::vector<std::vector<int>> dist(r, std::vector<int>(c, -1)); std::queue<std::pair<int, int>> q; dist[0][0] = 0; q.push({0, 0}); while (!q.empty()) { auto [y, x] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; q.push({ny, nx}); } } } return dist[r - 1][c - 1];} int main() { std::cin >> r >> c; grid.resize(r); for (auto& row : grid) std::cin >> row; std::cout << countIslands() << "\n" << shortestPath() << "\n";}#include <stdbool.h>#include <stdio.h> static int r, c;static char grid[50][52];static bool seen[50][50];static int dist[50][50];static const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; static bool is_land(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#';} /* 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) */static void fill(int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (is_land(ny, nx) && !seen[ny][nx]) fill(ny, nx); }} static int count_islands(void) { int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y][x]) { islands++; fill(y, x); } return islands;} /* 너비 우선 탐색(BFS): 칸마다 한 번만 넣으니 큐는 r*c칸이면 된다 */static int shortest_path(void) { static int qy[2500], qx[2500]; if (!is_land(0, 0) || !is_land(r - 1, c - 1)) return -1; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) dist[y][x] = -1; int head = 0, tail = 0; dist[0][0] = 0; qy[tail] = 0, qx[tail] = 0, tail++; while (head < tail) { int y = qy[head], x = qx[head]; head++; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (is_land(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; qy[tail] = ny, qx[tail] = nx, tail++; } } } return dist[r - 1][c - 1];} int main(void) { scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) scanf("%51s", grid[y]); printf("%d\n", count_islands()); printf("%d\n", shortest_path()); return 0;}// 칸 (y, x)는 목록에서 y * c + x 자리에 둔다(2,500칸이라 목록 하나에 들어간다)땅인가(y, x){ 返回 y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == "#";} // 깊이 우선 탐색(DFS)을 스택으로 — 크레이콘 재귀는 몇천 단계에서 멈춰서 2,500칸 섬은 위험하다섬세기(){ seen = 新列表(r * c, 假); islands = 0; 循环 (y = 0; y < r; y++) { 循环 (x = 0; x < c; x++) { 如果 (grid[y][x] == "#" && !seen[y * c + x]) { islands += 1; seen[y * c + x] = 真; stack = [y * c + x]; 当 (stack.数量 > 0) { cell = stack[stack.数量 - 1]; stack.按位置移除(stack.数量 - 1); cy = 数学.商(cell, c); cx = cell % c; 循环 (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; 如果 (땅인가(ny, nx) && !seen[ny * c + nx]) { seen[ny * c + nx] = 真; stack.添加(ny * c + nx); } } } } } } 返回 islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다. 칸마다 한 번만 넣으니 큐는 앞 자리(head)만 옮긴다가장짧은길(){ 如果 (!땅인가(0, 0) || !땅인가(r - 1, c - 1)) { 返回 -1; } dist = 新列表(r * c, -1); dist[0] = 0; queue = [0]; head = 0; 当 (head < queue.数量) { cell = queue[head]; head += 1; cy = 数学.商(cell, c); cx = cell % c; 循环 (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; 如果 (땅인가(ny, nx) && dist[ny * c + nx] == -1) { dist[ny * c + nx] = dist[cell] + 1; queue.添加(ny * c + nx); } } } 返回 dist[r * c - 1];} 크기 = 控制台.读数字();r = 크기[0];c = 크기[1];grid = [];循环 (i = 0; i < r; i++){ grid.添加(控制台.读行().去空白());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1];控制台.输出(섬세기());控制台.输出(가장짧은길());