By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,897 Members | 1,969 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,897 IT Pros & Developers. It's quick & easy.

Chambers in castle home assignment

P: 1
hi
i m a newbie,sushant
could anyone please help me out with this problem??

Chambers in a Castle
The floor plan of a castle indicates where the walls are. The outer boundary of the castle is always an unbroken wall. The castle has no doors, only openings in the walls that lead from one room to another. A chamber is a collection of rooms that are connected to each other by gaps in the walls. The problem is to:

1. Count the number of chambers in the castle.
2. Calculate the area of the largest chamber.

To simplify the problem, the floor of the castle is divided into square tiles. All walls lie at tile boundaries. The area of a chamber is specified in terms of the number of tiles inside the room (without counting the tiles occupied by the surrounding walls).

The figure below is an example of a floor plan. Each square is a tile. White tiles represent open space, while black tiles represent walls. In this castle, there are four chambers. The largest chamber has an area of 58.


Input Format
The first line of input will have two integers M and N, with 0 < M ≤ 500 and 0 < M ≤ 500. M represents the number of rows and N the number of columns in the floor plan.

This will be followed by M lines of input. Each of these M lines will be a sequence of 0's and 1's of length N, separated by spaces. A 0 represents an open tile (a white square), while a 1 represents a tile with a wall (a black square). The outer boundary of the castle will always consist of an unbroken wall.

Output Format
The output of your program should be exactly two lines, each line consisting of a single number. The first line should be the number of chambers. The second line should be the size of the largest chamber.
Sample Input
This is the input corresponding to the figure above.
15 19
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1
1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output
4
58

i know that we have to use dfs/bfs...but could anyone plz tell me how to implement n code it using c++??
Jun 5 '07 #1
Share this Question
Share on Google+
10 Replies


RedSon
Expert 5K+
P: 5,000
The experts on this site are more than happy to help you with your problems but they cannot do your assignment/program for you. Attempt the assignment/program yourself first and post questions regarding any difficulties you have or about a particular function of the code that you don't know how to achieve.

Please read the Posting Guidelines and particularly the Coursework Posting Guidlines.

Then when you are ready post a new question in this thread.

MODERATOR
Jun 5 '07 #2

AdrianH
Expert 100+
P: 1,251
Looks interesting though. Get back to us with what work you have done.

Why do you need to use dfs/bfs? There are no nodes with children for this to make any sense.


Adrian
Jun 5 '07 #3

Savage
Expert 100+
P: 1,764
Looks interesting though. Get back to us with what work you have done.

Why do you need to use dfs/bfs? There are no nodes with children for this to make any sense.


Adrian

Intresting indeed

Savage
Jun 5 '07 #4

RedSon
Expert 5K+
P: 5,000
Intresting indeed

Savage
Savage,

You are just padding your post count with responses like this :P. Shame on you!

lol
Jun 5 '07 #5

AdrianH
Expert 100+
P: 1,251
Savage,

You are just padding your post count with responses like this :P. Shame on you!

lol
Shame, shame! ;)


Adrian
Jun 5 '07 #6

100+
P: 208
Shame, shame! ;)


Adrian
You're doing it too!!
Oh wait...I'm doing it....ah crap.
Jun 5 '07 #7

Savage
Expert 100+
P: 1,764
We all should be ashamed.

:P

Savage
Jun 5 '07 #8

RedSon
Expert 5K+
P: 5,000
Ashamed, ashamed, ashamed. Say that ten times fast.
Jun 5 '07 #9

RedSon
Expert 5K+
P: 5,000
Okay now thats enough. What have I told you about hijacking a thread....?


Don't do it just to pad your thread count! Have a better reason!
Jun 5 '07 #10

100+
P: 208
Okay now thats enough. What have I told you about hijacking a thread....?


Don't do it just to pad your thread count! Have a better reason!
Sigh...ok.... I guess we should hav e better reason to post...

It's not like SushantK will come back and check this :P
Jun 5 '07 #11

Post your reply

Sign in to post your reply or Sign up for a free account.