Problem description

Below is a topographical map of a castle . Please write a program , Calculate the total number of rooms in the castle , How big is the biggest room . The castle is divided into m×n(m≤50,n≤50) Square block , Each square can have 0~4 face a wall .

input

Program reads data from standard input device .
The first line is two integers , North South , Number of blocks in east-west direction .

In the next input line , One number per square (0≤p≤50) describe . Use a number to represent the wall around the block ,1 West wall ,2 North wall ,4 East wall ,8 Representing the south wall . Each square is represented by the sum of numbers representing its surrounding walls . The castle's interior walls are counted twice , block (1,1) The south wall of is also a square (2,1) North wall .
The input data ensures that the castle has at least two rooms .

output

Number of rooms in the castle , The number of squares in the largest room in the castle .
The results are displayed on the standard output device

sample input

4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

sample output

5
9

Solving problems

According to the meaning , Let's find the destination from a starting point , And what's the longest route , To find the number of rooms is to find the number of polar connected subgraphs .

For every room , Depth first search , To give this room
Dyeing at all positions that can be reached between . Final statistics
Several colors , And the number of each color .
#include <iostream> #include <stack> #include <cstring> using namespace std;
int R, C; // Number of ranks int rooms; int color; // The mark of whether the square has been dyed int
maxRoomArea= 0, roomNum = 0; int roomArea; void Dfs(int i, int k) { if (color[i]
[k])// Judge if it's the end , If so, jump out return; ++roomArea;// If it's not the end , Dalian Tongtong +1 color[i][k] = roomNum;
//=0 House number // Determine which wall does not exist if ((rooms[i][k] & 1) == 0) Dfs(i, k - 1); // Westward if ((rooms[
i][k] & 2) == 0) Dfs(i - 1, k); // Northward if ((rooms[i][k] & 4) == 0) Dfs(i, k + 1);
// Eastward if ((rooms[i][k] & 8) == 0) Dfs(i + 1, k); // Southward } int main() { cin >> R >>
C; for (int i = 1; i <= R; ++i) for (int k = 1; k <= C; ++k) cin >> rooms[i][k];
// Enter wall face for each grid memset(color, 0, sizeof(color));// All set to 0 for (int i = 1; i <= R; ++
i) for (int k = 1; k <= C; ++k) { if (!color[i][k]) { ++roomNum; roomArea = 0;
Dfs(i, k); maxRoomArea =// Determine which room counts , Which one to give max max(roomArea, maxRoomArea); } }
cout<< roomNum << endl; cout << maxRoomArea << endl; }

Technology
Daily Recommendation