阿祁的部落格

CSES 1192 - Counting rooms 解題心得( 題目 )

解題概念:DFS

解題方法:我們走訪每個格子，如果這格沒被走過就room+1，並且把它塗黑(變成不是空的)，接著往四周走dfs，把屬於這個房間範圍的都塗黑。

Java參考程式碼(有更好意見可留言於下方，謝謝!)

import java.io.*;

import java.util.*;

public class cses1192 {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
    public static int r,ret,n,m;
 
    public static boolean[][] mp=new boolean[1005][1005];
 
    public static boolean oor;
 
    public static void main(String[] args) throws Exception {
 
       String a=br.readLine();
 
       String[] r=a.split(" ");
 
       n=Integer.parseInt(r[0]);
 
       m=Integer.parseInt(r[1]);
 
       int cnt=0;
 
       for(int i=1;i<=n;i++) {
 
           a=br.readLine();
 
           for(int j=1;j<=m;j++) {
 
               if(a.charAt(j-1)=='.')mp[i][j]=true;
 
           }
 
       }
 
       for(int i=1;i<=n;i++) {
 
           for(int j=1;j<=m;j++) {
 
               if(mp[i][j]) {
 
                   dfs(i,j);
 
                   cnt++;
 
               }
 
           }
 
       }
 
       System.out.println(cnt);
 
   }
 
   
 
   public static void dfs(int x,int y) {
 
       if(!mp[x][y])return;
 
       mp[x][y]=false;
 
       dfs(x-1,y);
 
       dfs(x+1,y);
 
       dfs(x,y-1);
 
       dfs(x,y+1);
 
   }

}