# The problem of “Castle on the Grid” – C++ Source code

T

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** 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;
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++) {

*(grid + i) = grid_item;
}

int grid_count = n;

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;
}

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;
}
```