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;
// Checks to see if cell is walled inside at a particular height (ignores if
walled at lower heights)
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[])
{
//Write code here
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++) {
// check if cell on boundaries
if(row==0 || row==rows-1 || column==0 || column==columns-1)
continue;
// for each cell, rise from the cell's top to the max height
possible(can be optimized)
// if at any height, cell is not walled, break loop for cell
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++;
}
else atHeight = maxHeight; // break height loop for cell
}
}
}
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/d6648250-9a00-4baf-a89f-0f9a42ddae04%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
