226 lines
6.7 KiB
C
226 lines
6.7 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#define BUFFER_SIZE 256
|
|
#define FIFO_MAX 1000
|
|
#define PATH_MAX FIFO_MAX
|
|
#define CLIMB_THRESHOLD 1
|
|
|
|
int explore(int [*][*][2], int, int, int*, int, int, char[*][*], int, int);
|
|
|
|
struct fifoentry {
|
|
};
|
|
|
|
// Store in a fifo what to explore and where did it come from
|
|
unsigned fifo[FIFO_MAX][4], fifo_tail = 0;
|
|
|
|
int main() {
|
|
char c;
|
|
int map_width = -1, col = 0, row = 0;
|
|
|
|
// It would be very impractical to dynamically try to allocate memory because
|
|
// we would have to collect the first row into a separate buffer and then copy it
|
|
// to our dynamically allocated array after reading the first row
|
|
char map[BUFFER_SIZE][BUFFER_SIZE];
|
|
int startPos[2], endPos[2];
|
|
|
|
while ((c = getchar()) != EOF) {
|
|
if (c == '\n') {
|
|
if (map_width == -1) map_width = col;
|
|
row++;
|
|
} else {
|
|
if (c == 'S') {
|
|
startPos[0] = col;
|
|
startPos[1] = row;
|
|
map[col][row] = 'a';
|
|
} else if (c == 'E') {
|
|
endPos[0] = col;
|
|
endPos[1] = row;
|
|
map[col][row] = 'z';
|
|
} else {
|
|
map[col][row] = c;
|
|
}
|
|
}
|
|
if (col == map_width) {
|
|
col = 0;
|
|
} else {
|
|
col++;
|
|
}
|
|
}
|
|
|
|
printf("Cols: %i, Rows: %i, Start: %i:%i, End: %i:%i\n", map_width, row, startPos[0], startPos[1], endPos[0], endPos[1]);
|
|
int visited[BUFFER_SIZE][BUFFER_SIZE][2];
|
|
|
|
for (int i = 0; i < row; i++) {
|
|
for (int j = 0; j < map_width; j++) {
|
|
visited[j][i][0] = -1;
|
|
visited[j][i][1] = -1;
|
|
}
|
|
}
|
|
|
|
// Let's climb
|
|
// We will have a FIFO, we pop the next move, and push all new paths to the end
|
|
// This way we will find the shortest path
|
|
int path_found = 0;
|
|
fifo[fifo_tail][0] = startPos[0];
|
|
fifo[fifo_tail][1] = startPos[1];
|
|
fifo[fifo_tail][2] = -2;
|
|
fifo[fifo_tail][3] = -2;
|
|
fifo_tail++;
|
|
|
|
while (!path_found) {
|
|
// Pop from the queue
|
|
int cCol = fifo[0][0];
|
|
int cRow = fifo[0][1];
|
|
int cFromCol = fifo[0][2];
|
|
int cFromRow = fifo[0][3];
|
|
|
|
for (int i = 0; i < fifo_tail - 1; i++) {
|
|
fifo[i][0] = fifo[i+1][0];
|
|
fifo[i][1] = fifo[i+1][1];
|
|
fifo[i][2] = fifo[i+1][2];
|
|
fifo[i][3] = fifo[i+1][3];
|
|
}
|
|
|
|
fifo_tail--;
|
|
|
|
// Explore the head
|
|
if (explore(visited, cCol, cRow, endPos, map_width, row, map, cFromCol, cFromRow)) {
|
|
path_found = 1;
|
|
}
|
|
}
|
|
|
|
// Now we have to backtrack
|
|
int numSteps = 0, last[2] = {visited[endPos[0]][endPos[1]][0], visited[endPos[0]][endPos[1]][1]};
|
|
while (last[0] != -2) {
|
|
int tmp[2] = {last[0], last[1]};
|
|
last[0] = visited[tmp[0]][tmp[1]][0];
|
|
last[1] = visited[tmp[0]][tmp[1]][1];
|
|
numSteps++;
|
|
}
|
|
|
|
printf("Steps from START: %i\n", numSteps);
|
|
|
|
// It will be at max numSteps
|
|
int minSteps = numSteps;
|
|
// Do this again with every 'a' point for part 2
|
|
// I just copy the code in a for loop, I ain't refactoring this
|
|
for (int i = 0; i < row; i++) {
|
|
for (int j = 0; j < map_width; j++) {
|
|
if (map[j][i] != 'a') {
|
|
continue;
|
|
}
|
|
startPos[0] = j;
|
|
startPos[1] = i;
|
|
|
|
// Reset visited
|
|
for (int i = 0; i < row; i++) {
|
|
for (int j = 0; j < map_width; j++) {
|
|
visited[j][i][0] = -1;
|
|
visited[j][i][1] = -1;
|
|
}
|
|
}
|
|
|
|
// Reset FIFO
|
|
path_found = 0, fifo_tail = 0;
|
|
fifo[fifo_tail][0] = startPos[0];
|
|
fifo[fifo_tail][1] = startPos[1];
|
|
fifo[fifo_tail][2] = -2;
|
|
fifo[fifo_tail][3] = -2;
|
|
fifo_tail++;
|
|
|
|
while (!path_found) {
|
|
// Pop from the queue
|
|
int cCol = fifo[0][0];
|
|
int cRow = fifo[0][1];
|
|
int cFromCol = fifo[0][2];
|
|
int cFromRow = fifo[0][3];
|
|
|
|
for (int i = 0; i < fifo_tail - 1; i++) {
|
|
fifo[i][0] = fifo[i+1][0];
|
|
fifo[i][1] = fifo[i+1][1];
|
|
fifo[i][2] = fifo[i+1][2];
|
|
fifo[i][3] = fifo[i+1][3];
|
|
}
|
|
|
|
fifo_tail--;
|
|
|
|
// Explore the head
|
|
if (explore(visited, cCol, cRow, endPos, map_width, row, map, cFromCol, cFromRow)) {
|
|
path_found = 1;
|
|
}
|
|
|
|
// We cannot traverse further, this is a dead end
|
|
if (fifo_tail == 0)
|
|
break;
|
|
}
|
|
|
|
// There might be cases when there isn't a path
|
|
if (path_found) {
|
|
numSteps = 0;
|
|
last[0] = visited[endPos[0]][endPos[1]][0];
|
|
last[1] = visited[endPos[0]][endPos[1]][1];
|
|
while (last[0] != -2) {
|
|
int tmp[2] = {last[0], last[1]};
|
|
last[0] = visited[tmp[0]][tmp[1]][0];
|
|
last[1] = visited[tmp[0]][tmp[1]][1];
|
|
numSteps++;
|
|
}
|
|
|
|
if (numSteps < minSteps) {
|
|
minSteps = numSteps;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
printf("Min Steps: %i\n", minSteps);
|
|
}
|
|
|
|
int explore(int visited[BUFFER_SIZE][BUFFER_SIZE][2], int col, int row, int* end, int mapWidth, int mapHeight, char map[BUFFER_SIZE][BUFFER_SIZE], int fromCol, int fromRow) {
|
|
if (visited[col][row][0] != -1) {
|
|
return 0;
|
|
}
|
|
|
|
visited[col][row][0] = fromCol;
|
|
visited[col][row][1] = fromRow;
|
|
|
|
if (col == end[0] && row == end[1]) {
|
|
return 1;
|
|
}
|
|
|
|
if (col < mapWidth - 1 && map[col + 1][row] <= map[col][row] + CLIMB_THRESHOLD) {
|
|
fifo[fifo_tail][0] = col + 1;
|
|
fifo[fifo_tail][1] = row;
|
|
fifo[fifo_tail][2] = col;
|
|
fifo[fifo_tail][3] = row;
|
|
fifo_tail++;
|
|
}
|
|
|
|
if (col > 0 && map[col - 1][row] <= map[col][row] + CLIMB_THRESHOLD) {
|
|
fifo[fifo_tail][0] = col - 1;
|
|
fifo[fifo_tail][1] = row;
|
|
fifo[fifo_tail][2] = col;
|
|
fifo[fifo_tail][3] = row;
|
|
fifo_tail++;
|
|
}
|
|
|
|
if (row < mapHeight - 1 && map[col][row + 1] <= map[col][row] + CLIMB_THRESHOLD) {
|
|
fifo[fifo_tail][0] = col;
|
|
fifo[fifo_tail][1] = row + 1;
|
|
fifo[fifo_tail][2] = col;
|
|
fifo[fifo_tail][3] = row;
|
|
fifo_tail++;
|
|
}
|
|
|
|
if (row > 0 && map[col][row - 1] <= map[col][row] + CLIMB_THRESHOLD) {
|
|
fifo[fifo_tail][0] = col;
|
|
fifo[fifo_tail][1] = row - 1;
|
|
fifo[fifo_tail][2] = col;
|
|
fifo[fifo_tail][3] = row;
|
|
fifo_tail++;
|
|
}
|
|
|
|
return 0;
|
|
}
|