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];コンソール.書く(섬세기());コンソール.書く(가장짧은길());