Here's a simple C program that searches if water can be contained at a
particular cell in a 3D grid and returns total volume:
#include<stdio.h>
#include<string.h>
#include <stdbool.h>
int rows;
int columns;
int *heightsArray;
bool hasWall(int row, int column, int atHeight, int directionIndex)
{
if(row==0 || row==rows-1 || column==0 || column==columns-1) return false;
// boundary check
if (directionIndex==1) { // up
if (heightsArray[(row-1)*columns + column] > atHeight)
return true;
else
return (hasWall(row-1, column, atHeight, 1) &&
hasWall(row-1, column, atHeight, 3) &&
hasWall(row-1, column, atHeight, 4));
}
else if (directionIndex==2) { // down
if (heightsArray[(row+1)*columns + column] > atHeight)
return true;
else
return (hasWall(row+1, column, atHeight, 2) &&
hasWall(row+1, column, atHeight, 3) &&
hasWall(row+1, column, atHeight, 4));
}
else if (directionIndex==3) { // left
if (heightsArray[row*columns + column - 1] > atHeight)
return true;
else
return (hasWall(row, column - 1, atHeight, 1) &&
hasWall(row, column - 1, atHeight, 2) &&
hasWall(row, column - 1, atHeight, 3));
}
else if (directionIndex==4) { // right
if (heightsArray[row*columns + column + 1] > atHeight)
return true;
else
return (hasWall(row, column + 1, atHeight, 1) &&
hasWall(row, column + 1, atHeight, 2) &&
hasWall(row, column + 1, atHeight, 4));
}
return false;
}
int GetWaterLevel(int input1, int input2, int input3[])
{
rows = input1;
columns = input2;
heightsArray = input3;
int total = 0;
int row = 0;
int column = 0;
int maxHeight = 0;
int atHeight = 0;
for (row = 0; row<rows*columns; row++)
if (input3[row]>maxHeight) maxHeight=input3[row];
for (row = 0; row<rows; row++) {
for (column = 0; column<columns; column++) {
if(row==0 || row==rows-1 || column==0 || column==columns-1)
continue;
for (atHeight = heightsArray[row*columns + column];
atHeight<maxHeight; atHeight++) {
if(hasWall(row, column, atHeight, 1) && // up
hasWall(row, column, atHeight, 2) && // down
hasWall(row, column, atHeight, 3) && // left
hasWall(row, column, atHeight, 4)) { // right
total++;
}
}
}
}
return total;
}
Call the function like so:
int inputArray[18] = {3,3,4,4,4,2, 3,1,3,2,1,4, 7,3,1,6,4,1};
int totalWater = GetWaterLevel(3, 6, inputArray);
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/f0756015-99d1-4fbb-9d7e-5e5c93d6549f%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
