You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and an end position, determine the number of moves it will take to get to the end position.

For example, you are given a grid with sides n=3 described as follows:
. . .
. X .
. . .

Your starting position (sX,sY) = (0,0) so you start in the top left corner. The ending position is (gX,gY)=(1,2) . The path is (0,0->(0,2)->(1,2). It takes 2 moves to get to the goal.

https://www.hackerrank.com/challenges/castle-on-the-grid

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

typedef pair<int, int> Node;
struct NodeDistance 
{
    Node node;
    int distance;
};

const int DIR_X[] = {0, 1,  0, -1};
const int DIR_Y[] = {1, 0, -1,  0};

// Complete the minimumMoves function below.
int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) 
{
    Node start(startX,startY), end(goalX,goalY);

    int grid_size = int(grid.size());
    vector<vector<bool>> visited(grid_size, vector<bool>(grid_size));

    queue<NodeDistance> q_distances;

    q_distances.push({start, 0});
    visited[start.first][start.second] = true;

    while (!q_distances.empty()) 
    {
        NodeDistance cnd = q_distances.front();
        q_distances.pop();

        if (cnd.node == end)
            return cnd.distance;

        int x = cnd.node.first;
        int y = cnd.node.second;

        for (int dir = 0; dir < 4; dir++) 
        {
            int dx = DIR_X[dir], dy = DIR_Y[dir];

            for (int i = x + dx, j = y + dy;
                 i < grid_size && i >= 0 && j < grid_size && j >= 0 && grid[i][j] == '.';
                 i = i + dx, j = j + dy) 
            {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    q_distances.push({{i, j}, cnd.distance + 1});
                }
            }
        }
    }
    return -1;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char** grid = malloc(n * sizeof(char*));

    for (int i = 0; i < n; i++) {
        char* grid_item = readline();

        *(grid + i) = grid_item;
    }

    int grid_count = n;

    char** startXStartY = split_string(readline());

    char* startX_endptr;
    char* startX_str = startXStartY[0];
    int startX = strtol(startX_str, &startX_endptr, 10);

    if (startX_endptr == startX_str || *startX_endptr != '\0') { exit(EXIT_FAILURE); }

    char* startY_endptr;
    char* startY_str = startXStartY[1];
    int startY = strtol(startY_str, &startY_endptr, 10);

    if (startY_endptr == startY_str || *startY_endptr != '\0') { exit(EXIT_FAILURE); }

    char* goalX_endptr;
    char* goalX_str = startXStartY[2];
    int goalX = strtol(goalX_str, &goalX_endptr, 10);

    if (goalX_endptr == goalX_str || *goalX_endptr != '\0') { exit(EXIT_FAILURE); }

    char* goalY_endptr;
    char* goalY_str = startXStartY[3];
    int goalY = strtol(goalY_str, &goalY_endptr, 10);

    if (goalY_endptr == goalY_str || *goalY_endptr != '\0') { exit(EXIT_FAILURE); }

    int result = minimumMoves(grid_count, grid, startX, startY, goalX, goalY);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!line) {
            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);
    } else {
        data = realloc(data, data_length + 1);

        data[data_length] = '\0';
    }

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);

        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

 



Author

Write A Comment