A map of R rows and C columns is given. '#' is land and '.' is water. Land cells touching up, down, left or right belong to the same island (diagonals do not connect). Print two lines. The first line is the number of islands. The second line is the fewest moves needed to go from the top-left cell to the bottom-right cell, stepping one cell up, down, left or right and only on land. If either of those cells is water or the trip is impossible, print -1; if the map is a single land cell, the answer is 0.
Input
The first line has R and C, followed by R strings of length C made only of '#' and '.'. 1 ≤ R, C ≤ 50
Output
First line: the number of islands; second line: the fewest moves, or -1
Example 1 · stdin
4 5
##..#
.#...
.####
#...#
stdout
3
7
Example 2 · stdin
2 2
#.
.#
stdout
2
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Counting islands is depth-first search (DFS): start from unseen land and mark all connected land; that is one island. The shortest route is breadth-first search (BFS): spread out from the nearest cells using a queue, and the distance when you first arrive is the answer — the first path DFS finds may be a detour. Recursive DFS is short, but depth is the problem: a long snake-shaped island recurses about 1,300 levels, which hits Python's default recursion limit of 1,000 and raises RecursionError — use a stack (list with append/pop) or raise sys.setrecursionlimit. Craykon recursion also stops at a few thousand levels, so it uses a list as a stack (Add and RemoveAt(Count - 1)). C, C++, Java, C# and JavaScript fit 2,500 levels of recursion in their default stacks. BFS queues: Python deque, Java ArrayDeque, C# Queue<(int, int)>, C++ std::queue<std::pair<int, int>>; C, JavaScript and Craykon add each cell only once, so an array plus a front index (head) is enough. 2D marker tables differ too: C# new bool[r, c] (a rectangular array), Java new boolean[r][c], and JavaScript must build a new array per row with Array.from (new Array(r).fill([]) makes every row the same array). Craykon stores it in one list at position y * c + x. Connecting diagonally changes the island count, so use only 4 directions.
Pythonmain.py · 52 lines
from collections import dequer, 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, nxdef 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 islandsdef 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())
JavaScriptmain.js · 48 lines
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());
TypeScriptmain.ts · 50 lines
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());
JavaMain.java · 69 lines
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()); }}
C#Main.cs · 73 lines
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()); }}
C++main.cpp · 60 lines
#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";}
Cmain.c · 63 lines
#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;}
Craykonmain.cray · 86 lines
// 칸 (y, x)는 목록에서 y * c + x 자리에 둔다(2,500칸이라 목록 하나에 들어간다)땅인가(y, x){ return y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == "#";}// 깊이 우선 탐색(DFS)을 스택으로 — 크레이콘 재귀는 몇천 단계에서 멈춰서 2,500칸 섬은 위험하다섬세기(){ seen = NewList(r * c, false); islands = 0; for (y = 0; y < r; y++) { for (x = 0; x < c; x++) { if (grid[y][x] == "#" && !seen[y * c + x]) { islands += 1; seen[y * c + x] = true; stack = [y * c + x]; while (stack.Count > 0) { cell = stack[stack.Count - 1]; stack.RemoveAt(stack.Count - 1); cy = Mathf.Quot(cell, c); cx = cell % c; for (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; if (땅인가(ny, nx) && !seen[ny * c + nx]) { seen[ny * c + nx] = true; stack.Add(ny * c + nx); } } } } } } return islands;}// 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다. 칸마다 한 번만 넣으니 큐는 앞 자리(head)만 옮긴다가장짧은길(){ if (!땅인가(0, 0) || !땅인가(r - 1, c - 1)) { return -1; } dist = NewList(r * c, -1); dist[0] = 0; queue = [0]; head = 0; while (head < queue.Count) { cell = queue[head]; head += 1; cy = Mathf.Quot(cell, c); cx = cell % c; for (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; if (땅인가(ny, nx) && dist[ny * c + nx] == -1) { dist[ny * c + nx] = dist[cell] + 1; queue.Add(ny * c + nx); } } } return dist[r * c - 1];}크기 = Console.ReadNumbers();r = 크기[0];c = 크기[1];grid = [];for (i = 0; i < r; i++){ grid.Add(Console.ReadLine().Trim());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1];Console.WriteLine(섬세기());Console.WriteLine(가장짧은길());