題目要求

題目鏈接

分析

這個題，很難直接確定那里是1這個邊界并找到內(nèi)部的0的，想想就很難受。

但是數(shù)學(xué)上有個思想叫 “正難則反” 不是嗎？

我們不妨把所有0換成2，再從四條邊上的每個點開DFS，把搜到的2全換成0，這種DFS不可能搜到內(nèi)部的2（被一圈1圍著），如此，巧妙的規(guī)避了“圈內(nèi)”這個復(fù)雜的條件，簡化了問題求解。

注意防越界！

AC代碼（Java語言描述）

import java.util.Scanner;public class Main {private static int num;private static byte[][] array;private static void dfs(int x, int y) {if (array[x][y] == 1) {return;} else {array[x][y] = 0;}if (x > 0 && array[x-1][y] == 2) {dfs(x-1, y);}if (x < num-1 && array[x+1][y] == 2) {dfs(x+1, y);}if (y > 0 && array[x][y-1] == 2) {dfs(x, y-1);}if (y < num-1 && array[x][y+1] == 2) {dfs(x, y+1);}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);num = Integer.parseInt(scanner.nextLine());array = new byte[num][num];for (int i = 0; i < num; i++) {String[] line = scanner.nextLine().split(" ");for (int j = 0; j < num; j++) {if ("0".equals(line[j])) {array[i][j] = 2;} else {array[i][j] = Byte.parseByte(line[j]);}}}scanner.close();for (int i = 0; i < num; i++) {dfs(i, 0);dfs(i, num-1);dfs(0, i);dfs(num-1, i);}for (int i = 0; i < num; i++) {StringBuilder builder = new StringBuilder();for (int j = 0; j < num; j++) {builder.append(array[i][j]).append(' ');}System.out.println(builder.toString().trim());}}}

總結(jié)

以上是生活随笔為你收集整理的填涂颜色（洛谷P1162题题解，Java语言描述）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。