Pavel 喜歡網格迷宮，一個網格迷宮是一個 n?×?m 的長方形迷宮，其中每個單元格要么是空白的，要么是墻體，您可以從一個單元格走到另一個單元格，只要兩個單元格均是空白的，且擁有一條公共的邊，
Pavel 繪制了一個網格迷宮，包含的全部空白單元格形成了一個連通區域，換言之，您可以從任何一個空白的單元格，走到其它任意的空白單元格，Pavel 的迷宮如果墻體太少，他就不喜歡這個迷宮，他希望將 k 個空白的單元格轉換為墻體，使得剩余的全部單元格仍然能夠形成一個連通區域，請幫助他實作這個任務，
輸入
第一行包含了三個整數 n, m, k (1?≤?n,?m?≤?500, 0?≤?k?<?s)，其中 n 和 m 分別是迷宮的高度和寬度，k 是 Pavel 希望加入的墻體數目，并且字母 s 表示原始迷宮中的空白單元格數目，
接下來的 n 行中，每行包含 m 個字符，它們描述了原始的迷宮，如果某行中的一個字符等于 "."，則相應的單元格為空白；如果字符等于 "#"，則單元格為墻體，
輸出
列印 n 行，每行包含 m 個字符：符合 Pavel 需求的新迷宮，將已轉換為墻體的原始空白單元格標識為 "X"；其它單元格必須保留為未更改狀態 (也就是 "." 和 "#")，
資料保證：存在一個解決方案，如果有多個解決方案，可輸出它們中的任意一個，
示例
輸入3 4 2輸出
#..#
..#.
#...
#.X#輸入
X.#.
#...
5 4 5輸出
#...
#.#.
.#..
...#
.#.#
#XXX
#X#.
X#..
...#
.#.#
思路：每次深搜洗掉葉節點，即每次深搜到底，洗掉深搜的最后一個元素
代碼：
import java.util.Scanner; public class Main{ static int n,m,k; static final int N=505; static char map[][]=new char[N][N]; static boolean vis[][]=new boolean[N][N]; static void dfs(int x,int y){ if(x<0 || y<0 || x>=n || y>=m) return; if(vis[x][y] || map[x][y]=='#') return; vis[x][y]=true; dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); // vis[x][y]=false; if(k>0){ map[x][y]='X'; k--; } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); k=scan.nextInt(); for(int i=0;i<n;i++) map[i]=scan.next().toCharArray(); for(int i=0;i<n&&k>0;i++) for(int j=0;j<m&&k>0;j++) if(map[i][j]=='.') dfs(i,j); for(int i=0;i<n;i++) System.out.println(map[i]); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98373.html
標籤：其他