The file consists of 50 lines of text. Each line consists of 3 sections: First is 3 characters made up of spaces and digits that you can ignore, then 80 characters which are either a space or a + then another 2 characters. The first 3 and last 2 characters are just 1 or 2 digits line numbers padded with spaces. The important part is the 80 characters.
The file would look something like this...
File starts here:
1 1
27 ++++++++ ++++ +++++++ ++++++++++++ +++ 27
28 ++++++++ ++++ +++++++ ++++++++++++ + ++++ ++++++ 28
This is a map of a game world where each location is either land or sea.Land points are +, sea are spaces. What you have to do is process the 80 x 50 map, determine how many continents there are and output how many continents there are plus a list of those continents, together with the size of each continent. The definition of a continent is one or more connected locations where each location is a +. Connected means that in a 3 x 3 grid around a +, if any of the 8 surrounding locations contains a + then the two are connected.
the map file can be downloaded from this location.
I present the code for this problem as below.
/* C++ */
/*
author : pranav prakash
country : india
email : pranavprakash@programmer.net
*/
#include < fstream.h >
char map[50][85];
int getMap(char*);
int scanContinent(int, int , int);
int findNext();
int getMap(char* mapfile){
fstream fl;
char v;
fl.open(mapfile, ios::in);
if(fl.bad() || fl.eof()){
return -1;
}
for(int i=0; i<50; i++){
for(int j=0; j<85; j++){
fl.read((char*)&v, sizeof(v));
map[i][j] = v;
}
}
return 1;
}
int findNext(){
int Xpos=0, Ypos=0, unit=0, i, j;
static int continent=1;
for(i=0; i<50; i++)
for(j=3; j<83; j++)
if(map[i][j] == '+'){
Xpos = i;
Ypos = j;
cout<<"\n\n--- Continent Number: "<< continent<<" ---";
//cout<<"\nXpos: "<< Xpos<<" Ypos: "<< Ypos<<"\n";
unit = scanContinent(Xpos, Ypos, continent++);
cout<<"\nNo. of units: "<< unit;
}
return 0; // No more continents left in the map;
}
int scanContinent(int seedX, int seedY, int continent){
static int count=0;
if(map[seedX][seedY] == '+'){
count++;
map[seedX][seedY] = continent;
scanContinent(seedX,seedY+1,continent);
scanContinent(seedX,seedY-1,continent);
scanContinent(seedX+1,seedY+1,continent);
scanContinent(seedX+1,seedY,continent);
scanContinent(seedX+1,seedY-1,continent);
scanContinent(seedX-1,seedY+1,continent);
scanContinent(seedX-1,seedY,continent);
scanContinent(seedX-1,seedY-1,continent);
}
return count;
}
void main(void){
if(getMap("map.txt")){
findNext();
}
}
The original problem statement can be viewed at this location.
This solution was actually selected as a correct solution and was in the top 20 codes. The actual content can be seen at this location.
No comments:
Post a Comment