Renovation
Source: aizu

Renovation
Problem Statement

Jack is planning to renovate his house to make his room as large as possible. However, since Jack doesn’t have much money, he wants to create a spacious room with minimal effort.

Jack’s house is represented as a grid with height $H$ and width $W$. Each cell in the grid is in one of the following states:

.: A floor that Jack can freely move through.
#: A wall that Jack cannot pass through.
S: The cell where Jack is currently located, which is also a floor.

Jack can move to adjacent floor cells in the grid, either up, down, left, or right. He cannot move outside the boundaries of his house.

In this renovation, Jack can destroy up to one wall and turn it into a floor. Determine the maximum number of cells Jack can reach from the currently located position after making this change.

Input

The input consists of a single test case of the following format.

$H$ $W$
$l_1$
$l_2$
$\vdots$
$l_H$


The first line contains two integers, $H$ and $W$, representing the height and width of the grid, respectively. Both $H$ and $W$ are between $2$ and $500$ (both inclusive).

The next $H$ lines each contain a string of length $W$, representing the grid. Each string $l_i$ consists of the characters . (floor), # (wall), and S (Jack’s starting position). It is guaranteed that the grid contains exactly one S.

Output

Output a single integer, the maximum number of cells Jack can reach from his starting position after optionally destroying one wall.

Sample Input 1
3 5
.#...
.####
#.#.S

Sample Output 1
6

Sample Input 2
3 7
.......
...S...
.......

Sample Output 2
21


C++ solution:
// AOJ #3638
// Renovation 2025.1.24

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    int start_r = -1, start_c = -1;
    for(int i=0;i<H;i++){
        cin >> grid[i];
        for(int j=0;j<W;j++) if(grid[i][j] == 'S'){
            start_r = i;
            start_c = j;
        }
    }
    
    // Directions: up, down, left, right
    vector<pair<int, int>> directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
    
    vector<vector<int>> component_id(H, vector<int>(W, 0));
    // BFS from S
    queue<pair<int, int>> q;
    q.push({start_r, start_c});
    component_id[start_r][start_c] = 1;
    int C_size = 1;
    while(!q.empty()){
        pair<int, int> current = q.front(); q.pop();
        int r = current.first, c = current.second;
        for(auto &[dr, dc] : directions){
            int nr = r + dr, nc = c + dc;
            if(nr >=0 && nr < H && nc >=0 && nc < W){
                if( (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component_id[nr][nc]==0 ){
                    component_id[nr][nc] = 1;
                    C_size++;
                    q.push({nr, nc});
                }
            }
        }
    }
    
    int current_id = 2;
    vector<int> component_size;
    component_size.push_back(0);
    component_size.push_back(C_size); // component_id=1
    for(int i=0;i<H;i++) {
        for(int j=0;j<W;j++) {
            if( (grid[i][j] == '.' || grid[i][j] == 'S') && component_id[i][j]==0 ){
                // Start BFS for new component
                queue<pair<int, int>> qq;
                qq.push({i, j});
                component_id[i][j] = current_id;
                int size = 1;
                while(!qq.empty()){
                    pair<int, int> curr = qq.front(); qq.pop();
                    int r = curr.first, c = curr.second;
                    for(auto &[dr, dc] : directions){
                        int nr = r + dr, nc = c + dc;
                        if(nr >=0 && nr < H && nc >=0 && nc < W){
                            if( (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component_id[nr][nc]==0 ){
                                component_id[nr][nc] = current_id;
                                size++;
                                qq.push({nr, nc});
                            }
                        }
                    }
                }
                component_size.push_back(size);
                current_id++;
            }
        }
    }
    
    int total_components = current_id;
    // Initialize last_seen array
    // To handle large component_ids, use a vector and resize accordingly
    vector<int> last_seen(total_components, 0);
    int wall_number = 0;
    int max_reachable = C_size;
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(grid[i][j] == '#'){
                bool adjacent_to_C = false;
                // Check if this wall is adjacent to C
                for(auto &[dr, dc] : directions){
                    int ni = i + dr, nj = j + dc;
                    if(ni >=0 && ni < H && nj >=0 && nj < W){
                        if(component_id[ni][nj] == 1){
                            adjacent_to_C = true;
                            break;
                        }
                    }
                }
                if(adjacent_to_C){
                    wall_number++;
                    int sum_other = 0;
                    for(auto &[dr, dc] : directions){
                        int ni = i + dr, nj = j + dc;
                        if(ni >=0 && ni < H && nj >=0 && nj < W){
                            int cid = component_id[ni][nj];
                            if(cid > 1 && last_seen[cid] != wall_number){
                                sum_other += component_size[cid];
                                last_seen[cid] = wall_number;
                            }
                        }
                    }
                    // After adding, also add the wall cell itself
                    int total = C_size + 1 + sum_other;
                    if(total > max_reachable){
                        max_reachable = total;
                    }
                }
            }
        }
    }
    cout << max_reachable << '\n';
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

type pos struct {
	r, c int
}

var dirs = []pos{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	// Read grid dimensions
	scanner.Scan()
	firstLine := scanner.Text()
	var H, W int
	fmt.Sscanf(firstLine, "%d %d", &H, &W)

	// Read grid and find starting position
	grid := make([]string, H)
	var start pos
	for i := 0; i < H; i++ {
		scanner.Scan()
		grid[i] = scanner.Text()
		if idx := strings.IndexByte(grid[i], 'S'); idx != -1 {
			start = pos{i, idx}
		}
	}

	// Initialize component IDs
	compID := make([][]int, H)
	for i := range compID {
		compID[i] = make([]int, W)
	}

	// BFS for starting component (component 1)
	q := []pos{start}
	compID[start.r][start.c] = 1
	cSize := 1

	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		for _, d := range dirs {
			nr, nc := p.r+d.r, p.c+d.c
			if nr >= 0 && nr < H && nc >= 0 && nc < W {
				if (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && compID[nr][nc] == 0 {
					compID[nr][nc] = 1
					cSize++
					q = append(q, pos{nr, nc})
				}
			}
		}
	}

	// Find other components
	currentID := 2
	compSizes := []int{0, cSize} // component 0 unused, component 1 is starting component

	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if (grid[i][j] == '.' || grid[i][j] == 'S') && compID[i][j] == 0 {
				// New component found
				q := []pos{{i, j}}
				compID[i][j] = currentID
				size := 1

				for len(q) > 0 {
					p := q[0]
					q = q[1:]
					for _, d := range dirs {
						nr, nc := p.r+d.r, p.c+d.c
						if nr >= 0 && nr < H && nc >= 0 && nc < W {
							if (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && compID[nr][nc] == 0 {
								compID[nr][nc] = currentID
								size++
								q = append(q, pos{nr, nc})
							}
						}
					}
				}
				compSizes = append(compSizes, size)
				currentID++
			}
		}
	}

	// Find maximum reachable area by breaking one wall
	maxReachable := cSize
	lastSeen := make([]int, currentID)
	wallNum := 0

	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if grid[i][j] == '#' {
				adjacentToC := false
				// Check if wall is adjacent to component 1
				for _, d := range dirs {
					ni, nj := i+d.r, j+d.c
					if ni >= 0 && ni < H && nj >= 0 && nj < W {
						if compID[ni][nj] == 1 {
							adjacentToC = true
							break
						}
					}
				}

				if adjacentToC {
					wallNum++
					sumOther := 0
					for _, d := range dirs {
						ni, nj := i+d.r, j+d.c
						if ni >= 0 && ni < H && nj >= 0 && nj < W {
							cid := compID[ni][nj]
							if cid > 1 && lastSeen[cid] != wallNum {
								sumOther += compSizes[cid]
								lastSeen[cid] = wallNum
							}
						}
					}
					total := cSize + 1 + sumOther // +1 for the wall cell itself
					if total > maxReachable {
						maxReachable = total
					}
				}
			}
		}
	}

	fmt.Println(maxReachable)
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] hw = br.readLine().split(" ");
        int H = Integer.parseInt(hw[0]);
        int W = Integer.parseInt(hw[1]);
        
        char[][] grid = new char[H][W];
        int startR = -1, startC = -1;
        for (int i = 0; i < H; i++) {
            String line = br.readLine();
            grid[i] = line.toCharArray();
            for (int j = 0; j < W; j++) {
                if (grid[i][j] == 'S') {
                    startR = i;
                    startC = j;
                }
            }
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] component = new int[H][W];
        List<Integer> componentSizes = new ArrayList<>();
        componentSizes.add(0); // dummy for 0 index

        // BFS for component 1 (starting from S)
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startR, startC});
        component[startR][startC] = 1;
        int c1Size = 1;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];
            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                    if ((grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component[nr][nc] == 0) {
                        component[nr][nc] = 1;
                        c1Size++;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
        }
        componentSizes.add(c1Size);

        // Check if all cells are already reachable
        if (c1Size == H * W) {
            System.out.println(c1Size);
            return;
        }

        // BFS for other components
        int currentId = 2;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if ((grid[i][j] == '.' || grid[i][j] == 'S') && component[i][j] == 0) {
                    q = new LinkedList<>();
                    q.offer(new int[]{i, j});
                    component[i][j] = currentId;
                    int size = 1;

                    while (!q.isEmpty()) {
                        int[] curr = q.poll();
                        int r = curr[0], c = curr[1];
                        for (int[] dir : dirs) {
                            int nr = r + dir[0], nc = c + dir[1];
                            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                                if ((grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component[nr][nc] == 0) {
                                    component[nr][nc] = currentId;
                                    size++;
                                    q.offer(new int[]{nr, nc});
                                }
                            }
                        }
                    }
                    componentSizes.add(size);
                    currentId++;
                }
            }
        }

        // Find maximum reachable area by breaking one wall
        int maxReachable = c1Size;
        int[] lastSeen = new int[currentId];
        int wallCount = 0;

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (grid[i][j] == '#') {
                    boolean adjacentToC1 = false;
                    Set<Integer> adjacentComponents = new HashSet<>();

                    for (int[] dir : dirs) {
                        int ni = i + dir[0], nj = j + dir[1];
                        if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
                            if (component[ni][nj] == 1) {
                                adjacentToC1 = true;
                            } else if (component[ni][nj] > 1) {
                                adjacentComponents.add(component[ni][nj]);
                            }
                        }
                    }

                    if (adjacentToC1) {
                        wallCount++;
                        int sumOther = 0;
                        for (int comp : adjacentComponents) {
                            if (lastSeen[comp] != wallCount) {
                                sumOther += componentSizes.get(comp);
                                lastSeen[comp] = wallCount;
                            }
                        }
                        int total = c1Size + 1 + sumOther;
                        if (total > maxReachable) {
                            maxReachable = total;
                        }
                    }
                }
            }
        }

        System.out.println(maxReachable);
    }
}

JavaScript solution:
const { Queue } = require('datastructures-js');

function main() {
    const fs = require('fs');
    const input = fs.readFileSync(0, 'utf8').trim().split('\n');
    const [H, W] = input[0].split(' ').map(Number);
    const grid = input.slice(1, H + 1).map(line => line.trim());
    
    let startR = -1, startC = -1;
    for (let i = 0; i < H; i++) {
        for (let j = 0; j < W; j++) {
            if (grid[i][j] === 'S') {
                startR = i;
                startC = j;
                break;
            }
        }
        if (startR !== -1) break;
    }
    
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const componentId = Array.from({ length: H }, () => Array(W).fill(0));
    
    // BFS for component 1 (starting from S)
    const q = new Queue();
    q.enqueue([startR, startC]);
    componentId[startR][startC] = 1;
    let cSize = 1;
    
    while (!q.isEmpty()) {
        const [r, c] = q.dequeue();
        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;
            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                if ((grid[nr][nc] === '.' || grid[nr][nc] === 'S') && componentId[nr][nc] === 0) {
                    componentId[nr][nc] = 1;
                    cSize++;
                    q.enqueue([nr, nc]);
                }
            }
        }
    }
    
    let currentId = 2;
    const componentSizes = [0, cSize]; // componentSizes[1] = cSize
    
    for (let i = 0; i < H; i++) {
        for (let j = 0; j < W; j++) {
            if ((grid[i][j] === '.' || grid[i][j] === 'S') && componentId[i][j] === 0) {
                const qq = new Queue();
                qq.enqueue([i, j]);
                componentId[i][j] = currentId;
                let size = 1;
                
                while (!qq.isEmpty()) {
                    const [r, c] = qq.dequeue();
                    for (const [dr, dc] of directions) {
                        const nr = r + dr;
                        const nc = c + dc;
                        if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                            if ((grid[nr][nc] === '.' || grid[nr][nc] === 'S') && componentId[nr][nc] === 0) {
                                componentId[nr][nc] = currentId;
                                size++;
                                qq.enqueue([nr, nc]);
                            }
                        }
                    }
                }
                componentSizes.push(size);
                currentId++;
            }
        }
    }
    
    const totalComponents = currentId;
    const lastSeen = Array(totalComponents).fill(0);
    let wallNumber = 0;
    let maxReachable = cSize;
    
    for (let i = 0; i < H; i++) {
        for (let j = 0; j < W; j++) {
            if (grid[i][j] === '#') {
                let adjacentToC = false;
                for (const [dr, dc] of directions) {
                    const ni = i + dr;
                    const nj = j + dc;
                    if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
                        if (componentId[ni][nj] === 1) {
                            adjacentToC = true;
                            break;
                        }
                    }
                }
                if (adjacentToC) {
                    wallNumber++;
                    let sumOther = 0;
                    for (const [dr, dc] of directions) {
                        const ni = i + dr;
                        const nj = j + dc;
                        if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
                            const cid = componentId[ni][nj];
                            if (cid > 1 && lastSeen[cid] !== wallNumber) {
                                sumOther += componentSizes[cid];
                                lastSeen[cid] = wallNumber;
                            }
                        }
                    }
                    const total = cSize + 1 + sumOther;
                    if (total > maxReachable) {
                        maxReachable = total;
                    }
                }
            }
        }
    }
    
    console.log(maxReachable);
}

main();

Python solution:
import sys
from collections import deque

def main():
    # Read input
    H, W = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    # Find starting position 'S'
    start_r, start_c = -1, -1
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 'S':
                start_r, start_c = i, j
                break
        if start_r != -1:
            break
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Initialize component IDs and sizes
    component_id = [[0 for _ in range(W)] for _ in range(H)]
    component_sizes = [0]  # component 0 unused
    
    # BFS for the component containing 'S' (component 1)
    q = deque()
    q.append((start_r, start_c))
    component_id[start_r][start_c] = 1
    component_size = 1
    
    while q:
        r, c = q.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W:
                if grid[nr][nc] in ('.', 'S') and component_id[nr][nc] == 0:
                    component_id[nr][nc] = 1
                    component_size += 1
                    q.append((nr, nc))
    
    component_sizes.append(component_size)
    
    # If all cells are reachable without breaking walls
    if component_size == H * W:
        print(component_size)
        return
    
    # BFS for other components
    current_id = 2
    for i in range(H):
        for j in range(W):
            if grid[i][j] in ('.', 'S') and component_id[i][j] == 0:
                q = deque()
                q.append((i, j))
                component_id[i][j] = current_id
                size = 1
                
                while q:
                    r, c = q.popleft()
                    for dr, dc in directions:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < H and 0 <= nc < W:
                            if grid[nr][nc] in ('.', 'S') and component_id[nr][nc] == 0:
                                component_id[nr][nc] = current_id
                                size += 1
                                q.append((nr, nc))
                
                component_sizes.append(size)
                current_id += 1
    
    # Check walls adjacent to component 1
    max_reachable = component_sizes[1]
    last_seen = [0] * current_id
    wall_number = 0
    
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                adjacent_to_C = False
                # Check if this wall is adjacent to component 1
                for dr, dc in directions:
                    ni, nj = i + dr, j + dc
                    if 0 <= ni < H and 0 <= nj < W:
                        if component_id[ni][nj] == 1:
                            adjacent_to_C = True
                            break
                
                if adjacent_to_C:
                    wall_number += 1
                    sum_other = 0
                    # Check adjacent components
                    for dr, dc in directions:
                        ni, nj = i + dr, j + dc
                        if 0 <= ni < H and 0 <= nj < W:
                            cid = component_id[ni][nj]
                            if cid > 1 and last_seen[cid] != wall_number:
                                sum_other += component_sizes[cid]
                                last_seen[cid] = wall_number
                    
                    # Total includes component 1, the wall cell, and connected components
                    total = component_sizes[1] + 1 + sum_other
                    if total > max_reachable:
                        max_reachable = total
    
    print(max_reachable)

if __name__ == '__main__':
    main()

Ruby solution:
def main
  # Read input dimensions
  h, w = gets.split.map(&:to_i)
  
  # Read grid and find starting position
  grid = []
  start_r = -1
  start_c = -1
  h.times do |i|
    line = gets.chomp
    grid << line
    if line.include?('S')
      start_r = i
      start_c = line.index('S')
    end
  end

  # Directions: up, down, left, right
  directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

  # Initialize component tracking
  component_id = Array.new(h) { Array.new(w, 0) }
  component_sizes = [0] # component 0 is unused

  # BFS for starting component (component 1)
  queue = [[start_r, start_c]]
  component_id[start_r][start_c] = 1
  c_size = 1

  until queue.empty?
    r, c = queue.shift
    directions.each do |dr, dc|
      nr = r + dr
      nc = c + dc
      if nr.between?(0, h-1) && nc.between?(0, w-1)
        if (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component_id[nr][nc] == 0
          component_id[nr][nc] = 1
          c_size += 1
          queue << [nr, nc]
        end
      end
    end
  end
  component_sizes << c_size

  # Find other components
  current_id = 2
  (0...h).each do |i|
    (0...w).each do |j|
      if (grid[i][j] == '.' || grid[i][j] == 'S') && component_id[i][j] == 0
        queue = [[i, j]]
        component_id[i][j] = current_id
        size = 1

        until queue.empty?
          r, c = queue.shift
          directions.each do |dr, dc|
            nr = r + dr
            nc = c + dc
            if nr.between?(0, h-1) && nc.between?(0, w-1)
              if (grid[nr][nc] == '.' || grid[nr][nc] == 'S') && component_id[nr][nc] == 0
                component_id[nr][nc] = current_id
                size += 1
                queue << [nr, nc]
              end
            end
          end
        end

        component_sizes << size
        current_id += 1
      end
    end
  end

  # Check walls adjacent to component 1
  max_reachable = c_size
  last_seen = Array.new(current_id, 0)
  wall_number = 0

  (0...h).each do |i|
    (0...w).each do |j|
      if grid[i][j] == '#'
        adjacent_to_c = false
        # Check if this wall is adjacent to component 1
        directions.each do |dr, dc|
          ni = i + dr
          nj = j + dc
          if ni.between?(0, h-1) && nj.between?(0, w-1)
            if component_id[ni][nj] == 1
              adjacent_to_c = true
              break
            end
          end
        end

        if adjacent_to_c
          wall_number += 1
          sum_other = 0
          directions.each do |dr, dc|
            ni = i + dr
            nj = j + dc
            if ni.between?(0, h-1) && nj.between?(0, w-1)
              cid = component_id[ni][nj]
              if cid > 1 && last_seen[cid] != wall_number
                sum_other += component_sizes[cid]
                last_seen[cid] = wall_number
              end
            end
          end
          total = c_size + 1 + sum_other
          max_reachable = [max_reachable, total].max
        end
      end
    end
  end

  puts max_reachable
end

main