Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- char * get_line(void);
- unsigned get_number(void);
- char ** get_lines(unsigned);
- char * check_line(char *, unsigned, unsigned);
- void free_lines_array(char **, unsigned);
- void initialize_grid(int *, unsigned, char **);
- int update_grid(int *, unsigned);
- int lowest_neighbour(int *, unsigned, unsigned, unsigned);
- int minimum(int, int);
- inline int * cell (int * grid, unsigned row, unsigned col, unsigned size) {
- return grid + (row * size + col);
- }
- int main (void) {
- unsigned size = get_number();
- if (!size) {
- fprintf(stderr, "Invalid size\n");
- return 1;
- }
- char ** lines = get_lines(size);
- unsigned line;
- for (line = 0; line < size; line ++) lines[line] = check_line(lines[line], size, line + 1);
- int * grid = malloc(sizeof(int) * size * size);
- initialize_grid(grid, size, lines);
- free_lines_array(lines, size);
- int result;
- do
- result = update_grid(grid, size);
- while (result == -1);
- free(grid);
- if (result > 0)
- printf("true, %d\n", result);
- else
- printf("false\n");
- return 0;
- }
- char * get_line (void) {
- char * line = NULL;
- unsigned length = 0;
- char newchar;
- for (newchar = getchar(); (newchar != EOF) && (newchar != '\n'); newchar = getchar()) {
- line = realloc(line, ++ length);
- line[length - 1] = newchar;
- }
- line = realloc(line, length + 1);
- line[length] = 0;
- return line;
- }
- unsigned get_number (void) {
- char * line = get_line();
- if (!*line) {
- free(line);
- return 0;
- }
- char * end;
- unsigned number = strtoul(line, &end, 10);
- if (*end) number = 0;
- free(line);
- return number;
- }
- char ** get_lines (unsigned lines) {
- char ** result = malloc(sizeof(char *) * lines);
- unsigned line;
- for (line = 0; line < lines; line ++) result[line] = get_line();
- return result;
- }
- char * check_line (char * line, unsigned size, unsigned line_number) {
- unsigned length = strlen(line);
- unsigned pos;
- if (length > size) {
- fprintf(stderr, "Line %u is %u characters long (expected: %u), truncating\n", line_number, length, size);
- line = realloc(line, size + 1);
- line[size] = 0;
- } else if (length < size) {
- fprintf(stderr, "Line %u is %u characters long (expected: %u), padding with dots\n", line_number, length, size);
- line = realloc(line, size + 1);
- memset(line + length, '.', size - length);
- line[size] = 0;
- }
- for (pos = 0; pos < size; pos ++) {
- if ((line[pos] == '.') || (line[pos] == 'W') || (line[pos] == 'E') || (line[pos] == 'S')) continue;
- fprintf(stderr, "Line %u: spurious character 0x%02x at column %u, inserting dot\n", line_number, (int) (line[pos]), pos + 1);
- line[pos] = '.';
- }
- return line;
- }
- void free_lines_array (char ** lines, unsigned size) {
- unsigned line;
- for (line = 0; line < size; line ++) free(lines[line]);
- free(lines);
- }
- void initialize_grid (int * grid, unsigned size, char ** lines) {
- unsigned row, col;
- for (row = 0; row < size; row ++)
- for (col = 0; col < size; col ++)
- switch(lines[row][col]) {
- case 'E': *cell(grid, row, col, size) = -3; break;
- case 'S': *cell(grid, row, col, size) = 0; break;
- case 'W': *cell(grid, row, col, size) = -2; break;
- default: *cell(grid, row, col, size) = -1;
- }
- }
- int update_grid (int * grid, unsigned size) {
- int * oldgrid = malloc(sizeof(int) * size * size);
- memcpy(oldgrid, grid, sizeof(int) * size * size);
- unsigned row, col;
- int update, updated = -2;
- for (row = 0; row < size; row ++)
- for (col = 0; col < size; col ++)
- switch (*cell(grid, row, col, size)) {
- case -1:
- update = lowest_neighbour(oldgrid, row, col, size);
- if (update >= 0) {
- *cell(grid, row, col, size) = update + 1;
- updated = -1;
- }
- break;
- case -3:
- update = lowest_neighbour(oldgrid, row, col, size);
- if (update >= 0) {
- free(oldgrid);
- return update + 1;
- }
- }
- free(oldgrid);
- return updated;
- }
- int lowest_neighbour (int * grid, unsigned row, unsigned col, unsigned size) {
- int result = -1;
- if (row) result = minimum(result, *cell(grid, row - 1, col, size));
- if (col) result = minimum(result, *cell(grid, row, col - 1, size));
- if ((row + 1) < size) result = minimum(result, *cell(grid, row + 1, col, size));
- if ((col + 1) < size) result = minimum(result, *cell(grid, row, col + 1, size));
- return result;
- }
- int minimum (int n1, int n2) {
- if ((n1 < 0) && (n2 < 0)) return -1;
- if (n1 < 0) return n2;
- if ((n2 < 0) || (n1 < n2)) return n1;
- return n2;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement