Skip to content

Instantly share code, notes, and snippets.

@darklight721
Created February 11, 2013 09:04
Show Gist options
  • Save darklight721/4753375 to your computer and use it in GitHub Desktop.
Save darklight721/4753375 to your computer and use it in GitHub Desktop.
#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