Count the Ships

Count the number of ships in an N×N grid where ships are connected '#' cells in any of 8 directions

Understand the Problem

Problem Statement

Count the Ships: A sea is represented as an N×N matrix where # represents a part of a ship and - represents water. All ships are surrounded by water. Series of # which are connected together forms a ship. The # can be connected to another # in any of the surrounding 8 cells to form a ship. The program must print the number of ships in the given map.

Constraints

1 ≤ N ≤ 100
Grid contains only '#' and '-' characters
Ships are connected via 8-directional adjacency (horizonal, vertical, diagonal)
Ships are surrounded by water (boundary cells are water)
Time limit: 1 second
Memory limit: 256 MB

Examples

Example 1

Input

6
------
-###--
-###--
------
-####-
-####-

Output

Explanation

There are two separate ships: one 2×3 rectangle in the middle and one 2×4 rectangle at the bottom. The ships are not connected to each other.

Example 2

Input

8
--#-----
--#-----
--#-----
-----#--
------#-
--#----#
#####---
--#-----

Output

Explanation

There are three ships: one vertical line on the left, one L-shaped ship in the bottom-left, and one diagonal chain of single cells on the right side.

Solution

#include <stdio.h>
#include <stdlib.h>

// Flood fill function to mark connected ship parts
void floodFill(char grid[][101], int n, int row, int col) {
    // Base case: out of bounds or not a ship part
    if (row < 0 || row >= n || col < 0 || col >= n || grid[row][col] != '#') {
        return;
    }
    
    // Mark current cell as visited
    grid[row][col] = '-';
    
    // Recursively flood fill in all 8 directions
    floodFill(grid, n, row-1, col-1); // top-left
    floodFill(grid, n, row-1, col);   // top
    floodFill(grid, n, row-1, col+1); // top-right
    floodFill(grid, n, row, col-1);   // left
    floodFill(grid, n, row, col+1);   // right
    floodFill(grid, n, row+1, col-1); // bottom-left
    floodFill(grid, n, row+1, col);   // bottom
    floodFill(grid, n, row+1, col+1); // bottom-right
}

int main() {
    int n;
    scanf("%d", &n);
    
    char grid[101][101];
    
    // Read grid
    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }
    
    int shipCount = 0;
    
    // Count connected components
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '#') {
                shipCount++;
                floodFill(grid, n, i, j);
            }
        }
    }
    
    printf("%d\n", shipCount);
    return 0;
}

Time:O(N²) - In worst case, we visit every cell once

Space:O(N²) - Recursion stack depth could be N² in worst case for a fully connected grid

Approach:

The C solution implements a classic flood fill algorithm:

Grid Reading: Uses a 2D char array of size 101×101 (max constraint +1 for null terminator)
Flood Fill Function: Recursively visits all 8-connected neighbors when a '#' is found
Marking Visited: Changes '#' to '-' to prevent revisiting the same ship part
Main Loop: Iterates through entire grid, counting new ships and immediately flood filling them
Complexity: O(N²) time and O(N²) space for recursion stack in worst case

Visual Explanation

Loading diagram...

All Problems