Created
February 11, 2013 09:04
-
-
Save darklight721/4753375 to your computer and use it in GitHub Desktop.
My solution to http://www.reddit.com/r/dailyprogrammer/comments/17jvoh/013013_challenge_119_intermediate_find_the/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
int ** makeGrid(int size, int *startX, int *startY, int *endX, int *endY) | |
{ | |
// allocate memory for the grid | |
int **grid = (int**)malloc(sizeof(int*) * size); | |
int x, y; | |
for (x = 0; x < size; x++) { | |
grid[x] = (int*)malloc(sizeof(int) * size); | |
for (y = 0; y < size; y++) { | |
grid[x][y] = -1; | |
} | |
} | |
flushall(); | |
for (y = 1; y < size - 1; y++) { | |
for (x = 1; x < size - 1; x++) { | |
char type = getchar(); | |
switch (type) { | |
case 'S': | |
grid[x][y] = INT_MAX; | |
*startX = x; | |
*startY = y; | |
break; | |
case 'E': | |
grid[x][y] = INT_MAX; | |
*endX = x; | |
*endY = y; | |
break; | |
case '.': | |
grid[x][y] = INT_MAX; | |
break; | |
case 'W': | |
default: | |
grid[x][y] = -1; | |
break; | |
} | |
} | |
while (getchar() != '\n'); | |
} | |
return grid; | |
} | |
void solveGrid(int **grid, int size, int nextX, int nextY, int nextStep) | |
{ | |
if (grid[nextX][nextY] < nextStep) { | |
return; | |
} | |
grid[nextX][nextY] = nextStep++; | |
for (int i = -1; i <= 1; i += 2) { | |
solveGrid(grid, size, nextX + i, nextY, nextStep); | |
solveGrid(grid, size, nextX, nextY + i, nextStep); | |
} | |
} | |
void freeGrid(int **grid, int size) | |
{ | |
if (grid) { | |
for (int x = 0; x < size; x++) { | |
if (grid[x]) { | |
free(grid[x]); | |
} | |
} | |
free(grid); | |
grid = NULL; | |
} | |
} | |
int main(void) | |
{ | |
int **grid, size, startX, startY, endX, endY; | |
// get grid's size | |
scanf("%d", &size); | |
// add 2 for the outer boundary | |
size += 2; | |
// form the grid from user's input | |
grid = makeGrid(size, &startX, &startY, &endX, &endY); | |
// solve the maze | |
solveGrid(grid, size, startX, startY, 0); | |
if (grid[endX][endY] == INT_MAX) { | |
printf("False"); | |
} | |
else { | |
printf("True, %d", grid[endX][endY]); | |
} | |
// free up grid | |
freeGrid(grid, size); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment