Counting Rooms

You are given a map of a building, and your task is to count the number of its rooms. The size of the map is n×m$n\times m$ squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.

Example:

Input:  n = 5, m = 8, board = {{"########", "#..#...#", "####.#.#", "#..#...#", "########"}}
Output: 3

Approach

Java

public class CountingRooms {
    public static void main(String[] args) {

        n = 5;
        m = 8;
        char board[][] = { { '#', '#', '#', '#', '#', '#', 
                           '#', '#' }, 
                       { '#', '.', '.', '#', '.', '.',
                             '.', '#' },
                { '#', '#', '#', '#', '.', '#', '.', '#' }, 
      { '#', '.', '.', '#', '.', '.', '.', '#' },
                { '#', '#', '#', '#', '#', '#', '#', '#' } };
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                grid[i][j] = board[i - 1][j - 1];
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (vis[i][j] == 0 && grid[i][j] == '.') {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    static char grid[][] = new char[10001][10001];

    static int dx[] = { -1, 0, 1, 0 };
    static int dy[] = { 0, 1, 0, -1 };
    static int vis[][] = new int[10001][10001];
    static int n;

    static int m;

    static boolean isValid(int x, int y) {
        if (x < 1 || x > n || y < 1 || y > m)
            return false;
        if (vis[x][y] == 1 || grid[x][y] == '#')
            return false;
        return true;
    }

    static void dfs(int x, int y) {
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            if (isValid(x + dx[i], y + dy[i]))
                dfs(x + dx[i], y + dy[i]);
        }
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
char grid[10001][10001];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[10001][10001];
int n, m;
bool isValid(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return false;
    if (vis[x][y] == 1 || grid[x][y] == '#')
        return false;
    return true;
}
void dfs(int x, int y)
{
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        if (isValid(x + dx[i], y + dy[i]))
            dfs(x + dx[i], y + dy[i]);
    }
}
int main()
{
    n = 5, m = 8;
    vector<string> board = {{"########",
                             "#..#...#",
                             "####.#.#",
                             "#..#...#",
                             "########"}};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            grid[i][j] = board[i - 1][j - 1];
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (vis[i][j] == 0 && grid[i][j] == '.')
            {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt << "\n";
}