On Tuesday, April 26, 2016 at 12:36:30 AM UTC+5:30, Aakash Chaudhary wrote:
> 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);
Hi Akash,
I am not sure whether your algo works for all the scenario or not .. but to
improve the performance why dont you update your for loops as below :
"
for (row = 1; row<rows-1; row++) {
for (column = 1; column<columns-1; column++) {
"
Coz anyway you are already doing a check that water cannot be accumulated at
the borders , so whats the point in running that loop for that condition ?
Hope you you got what I am trying to say.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/6b4a6948-6a52-4f5c-829e-c088d2bbf9e8%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
