Loading...

poj 2386 水溜まり。

Javaです。 勉強がてらチャレンジ。探索問題 深さ優先探索(DFS:Depth-First Search)の問題らしい。遷移できなくなるまで調べる。再帰にマッチするらしい。
package p2386; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); char[][] cs = new char[n][m]; scanner.skip("\n"); for (int i = 0; i < n; i++) { // char[] cs2 = new char[m]; cs[i] = scanner.nextLine().toCharArray(); } System.out.println(solve(cs)); } /** * 解く * * @param cs * @return */ public static int solve(char[][] cs) { int c = 0; for (int y = 0; y < cs.length; y++) { for (int x = 0; x < cs[y].length; x++) { if (cs[y][x] == 'W') { dfs(cs, x, y); c++; } } } return c; } /** * * @param cs * @param x * @param y */ static void dfs(char[][] cs, int x, int y) { // 検査済み cs[y][x] = '.'; /* * 8方向調べる。水溜まりならそこから調べる。 */ for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { int nx = x + dx; int ny = y + dy; if (0 <= nx && nx < cs[y].length && 0 <= ny && ny < cs.length && cs[ny][nx] == 'W') { dfs(cs, nx, ny); } } } } }
リアクション: 
poj 1902537553792416395

コメントを投稿

ホーム item

このブログを検索

Random Posts

Popular Posts

Labels

ADS