I'm practicing for a competition (that's where my previous question came from). I got the algorithm sorted out for the question, but I'm having some problems with the actual programming. It's a solo competition, so I really need to get this sorted out before I go for it. This is the question.
TASK 3: GECKO During the rainy season, one of the walls in the house is infested with mosquitoes. The wall is covered by h × w square tiles, where there are h rows of tiles from top to bottom, and w columns of tiles from left to right. Each tile has 1 to 1000 mosquitoes resting on it. A gecko wants to eat as many mosquitoes as possible, subject to the following restrictions. It starts by choosing any tile in the top row, and eats the mosquitoes in that tile. Then, it moves to a tile in the next lower row, eats the mosquitoes on the tile, and so on until it reaches the floor. When it moves from one tile to a tile in the next lower row, it can only move vertically down or diagonally to the left or right (see Figure 1). Given the values of h and w, and the number of mosquitoes resting on each tile, write a program to compute the maximum possible number of mosquitoes the gecko can eat in one single trip from the top to the bottom of the wall.
An example input file would be:
Example6 5
3 1 7 4 2
2 1 3 1 1
1 2 1 1 8
2 2 1 5 3
2 1 4 4 4
5 7 2 5 1
The problem I have is in reading in the numbers (or the top of the list of problems). My current code for reading in is:
ifstream read;
read.open("input.txt");
write.open("output.txt");
int width, height, wall[500][500];
read >> height;
read >> width;
for ( int count1 = 0; count1 < height; count1++)
{
for ( int count2 = 0; count2 < width; count2++)
{
read >> wall[count1][count2];
}
}
When I tested it with a cout to print all the numbers read in, all i got was gibberish.
Right now I can't spot any errors with it, can anyone see the problem? Thanks.
(fixed) Thanks again.
I tested the read in and it's perfect now. However, the number of flies I'm getting is still off. For example the input
1 1
23
Should give the output 23, but I'm getting 0 as an output.
Here's my code:
int h = 0, w = 0, compare1, compare2, compare3, currentInt;
for ( int count3=( height-2 ); count3 >= 0; count3--)
{
for( int count4 = 0; count4 < width; count4++)
{
h = count3;
w = count4;
currentInt = wall[h][w]; // read in affected integers.
if( w != 0 )
{ compare1 = wall[h+1][w-1];
}
compare2 = wall[h+1][w];
compare3 = wall[h+1][w+1];
if( w!= 0) // Compare and replace.
{
if((( currentInt + compare1) >=(currentInt + compare2)) && ((currentInt + compare1)>=(currentInt + compare3)))
{
wall[h][w] = ( currentInt+compare1);
}
if((( currentInt + compare2) >(currentInt + compare1)) && ((currentInt + compare2)>(currentInt + compare3)))
{
wall[h][w] = ( currentInt+compare2);
}
if((( currentInt + compare3) >=(currentInt + compare2)) && ((currentInt + compare1)>(currentInt + compare1)))
{
wall[h][w] = ( currentInt + compare3);
}
}
else
{
if ((currentInt + compare2) >= ( currentInt + compare3))
{
wall[h][w] = ( currentInt + compare2);
}
else
{
wall[h][w] = ( currentInt + compare3);
}
}
}
}
int maxFlies=0;
for (int count5 = 1; count5 < width;count5++)
{
maxFlies = wall[0][0] ;
if ( maxFlies < wall[0][count5])
{ maxFlies = wall[0][count5] ; }
}
write<<maxFlies<<endl;
read.close();
write.close();
return 0;
What I'm trying to do with that is basically: Read in from the second last line. Add it with the only blocks it can reach below. Then move up and finally test which one at the top line is the biggest integer. Thanks for the fast replies.
