- 2020-03-27 09:07
*views 1*- Learning algorithm knowledge points

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[60][60]; int color[60][60]; // 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

views 26

views 2

©2019-2020 Toolsou All rights reserved,

One is called “ Asking for the train ” A small village Finally got the train Spring Boot Lesson 16 ：SpringBoot Implementation of multithreading with injection class Chrome OS, For programmers and Windows What does it mean ? Internet Marketing JAVA Convert a string to a numeric type I've been drinking soft water for three years ? What is the use of soft water and water softener You don't know ——HarmonyOS Talking about uni-app Page value transfer problem JavaScript Medium Call and ApplySparkSQL Achieve partition overlay write Character recognition technology of vehicle license plate based on Neural Network