Counting Connected Chess Piece Blocks

In this problem, you are given an empty N×N chessboard onto which M chess pieces have been randomly placed. Each chess piece is either black or white, denoted by '*' (black) and '@' (white) respectively. Two pieces of the same color are considered connected if they are in adjacent cells (up, down, left, or right). A connected block is defined as a maximal set of pieces that are connected directly or indirectly.

Your task is to compute the total number of connected blocks on the board.

Note:

• The board is indexed from 1 to N for both rows and columns.
• Cells that do not have any chess piece are considered empty.

Example:

Input:
5 7
1 2 *
1 3 *
2 3 *
3 5 @
3 6 @
4 5 @
5 1 *
Explanation:
The board of size 5×5 has three connected blocks:

Block with '*' at positions (1,2), (1,3), (2,3).
Block with '@' at positions (3,5), (3,6), (4,5).
A solitary '*' at (5,1).

Output: 3

inputFormat

The first line contains two integers N and M separated by a space, where N is the size of the chessboard and M is the number of chess pieces placed on the board.

The next M lines each contain a description of one chess piece with three space-separated items: an integer r, an integer c (the row and column position of the piece, 1-indexed), and a character that is either '*' (representing a black piece) or '@' (representing a white piece).

outputFormat

Output a single integer representing the number of connected blocks on the board.

sample

5 7
1 2 *
1 3 *
2 3 *
3 5 @
3 6 @
4 5 @
5 1 *

3