447 lines
15 KiB
C
447 lines
15 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <stdbool.h>
|
|
|
|
typedef struct {
|
|
int rows;
|
|
int cols;
|
|
unsigned char *cells;
|
|
} Map;
|
|
|
|
#define RIGHT_HAND 0
|
|
#define LEFT_HAND 1
|
|
|
|
#define LEFT_BORDER 0
|
|
#define RIGHT_BORDER 1
|
|
#define TOP_BORDER 2
|
|
|
|
bool isborder(Map *map, int r, int c, int border);
|
|
int start_border(Map *map, int r, int c, int leftright);
|
|
Map* init_map(int rows, int cols);
|
|
void load_map(Map* map, const char* filename);
|
|
void free_map(Map* map);
|
|
bool validate_map(Map* map);
|
|
void find_path(Map* map, int r, int c, int leftright, int sborder);
|
|
int load_mapsize(int* mrow, int* mcol, const char* filename);
|
|
|
|
bool isborder(Map *map, int r, int c, int border) // kontroluje, ci na konkretnej bunke sa nachadza konkretna stena
|
|
{
|
|
unsigned char cell = map->cells[r * map->cols + c];
|
|
return (cell & (1 << border)) != 0; // ak sa stena bunky zhoduje s typom kontrolovanej steny, vrati true, inak false
|
|
}
|
|
|
|
int start_border(Map *map, int r, int c, int leftright) //zistenie zaciatocnej steny podla zadania
|
|
// a kontrola, ci zaciatocna bunka moze byt
|
|
// vstupna bunka bludiska
|
|
{
|
|
if (leftright == RIGHT_HAND)
|
|
{
|
|
if (c == 0 && r % 2 == 0 && !isborder(map, r, c, LEFT_BORDER)) return RIGHT_BORDER; // r je v nasej matici o 1 mensie, teda parny, obdobne dalsi if
|
|
else if (c == 0 && r % 2 == 1 && !isborder(map, r, c, LEFT_BORDER)) return TOP_BORDER;
|
|
else if (c == map->cols - 1 && ((r+c)%2==0) && !isborder(map, r, c, RIGHT_BORDER)) return TOP_BORDER;
|
|
else if (c == map->cols - 1 && ((r+c)%2==1) && !isborder(map, r, c, RIGHT_BORDER)) return LEFT_BORDER;
|
|
else if (r == 0 && !isborder(map, r, c, TOP_BORDER)) return LEFT_BORDER;
|
|
else if (r == map->rows - 1 && !isborder(map, r, c, TOP_BORDER)) return RIGHT_BORDER;
|
|
else return -1;
|
|
} else if (leftright == LEFT_HAND)
|
|
{
|
|
if (c == 0 && r % 2 == 0 && !isborder(map, r, c, LEFT_BORDER) ) return TOP_BORDER;
|
|
else if (c == 0 && r % 2 == 1 && !isborder(map, r, c, LEFT_BORDER)) return RIGHT_BORDER;
|
|
else if (c == map->cols - 1 && ((r+c)%2==0) && !isborder(map, r, c, RIGHT_BORDER)) return LEFT_BORDER;
|
|
else if (c == map->cols - 1 && ((r+c)%2==1) && !isborder(map, r, c, RIGHT_BORDER)) return TOP_BORDER;
|
|
else if (r == 0 && !isborder(map, r, c, TOP_BORDER)) return RIGHT_BORDER;
|
|
else if (r == map->rows - 1 && !isborder(map, r, c, TOP_BORDER)) return LEFT_BORDER;
|
|
else return -1;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
Map* init_map(int rows, int cols) { //inicializacia mapy
|
|
Map* map = malloc(sizeof(Map)); // alokujeme najprv miesto pre strukturu map
|
|
map->rows = rows;
|
|
map->cols = cols;
|
|
map->cells = malloc(rows * cols * sizeof(unsigned char)); // alokujeme miesto pre dany pocet buniek(rows * cols)
|
|
return map;
|
|
}
|
|
|
|
void load_map(Map* map, const char* filename) { //nacitanie mapy zo suboru
|
|
FILE *file = fopen(filename, "r");
|
|
if (file == NULL) {
|
|
fprintf(stderr,"File opening failed\n");
|
|
return;
|
|
}
|
|
fscanf(file, "%d %d", &(map->rows), &(map->cols));
|
|
for (int i = 0; i < map->rows; i++) {
|
|
for (int j = 0; j < map->cols; j++) {
|
|
fscanf(file, "%hhu", &(map->cells[i * map->cols + j]));
|
|
}
|
|
}
|
|
fclose(file);
|
|
}
|
|
|
|
void free_map(Map* map) { //uvolnenie mapy
|
|
free(map->cells);
|
|
free(map);
|
|
}
|
|
|
|
bool validate_map(Map* map) { //overenie spravnosti bludiska, kontrolujeme, ci je policko definovane validnym cislo(<=7)
|
|
for (int i = 0; i < map->rows; i++) {
|
|
for (int j = 0; j < map->cols; j++) {
|
|
unsigned char cell = map->cells[i * map->cols + j];
|
|
if (cell > 7) {
|
|
return false;
|
|
}
|
|
if (i > 0 && ((cell & (1 << TOP_BORDER)) != (map->cells[(i-1) * map->cols + j] & (1 << TOP_BORDER))) && ((j + i) % 2 == 0)) {
|
|
return false;
|
|
}
|
|
if (j > 0 && ((cell & (1 << LEFT_BORDER)) != ((map->cells[i * map->cols + (j-1)] & (1 << RIGHT_BORDER))>>RIGHT_BORDER))) { // pravu stenu popisuje druhy najnizsi bit
|
|
//a teda ho musime posunut na najnizsi, aby
|
|
//sa mohol porovnat s lavou stenou, ktora je
|
|
//na najnizsom bite
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void find_path(Map* map, int r, int c, int leftright, int sborder) { //hladanie cesty bludiskom
|
|
int x = r, y = c;
|
|
int current_border = sborder;// aktualna stena
|
|
int next_border; // nasledujuca stena
|
|
|
|
while ((x >= 0) && (x <= (map->rows - 1)) && (y >= 0) && (y <= map->cols - 1))
|
|
{ //kym nevyjdeme mimo bludiska
|
|
//v if vetvach hladame dalsiu stenu, na ktorej ma byt polozena ruka
|
|
printf("%d,%d\n", x + 1, y + 1);
|
|
if (leftright == RIGHT_HAND) { //podla pravidla pravej ruky
|
|
if (current_border == TOP_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = LEFT_BORDER;x++;
|
|
} else if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = RIGHT_BORDER;y++;
|
|
} else {
|
|
next_border = TOP_BORDER;y--;
|
|
}}
|
|
else if (current_border == TOP_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = RIGHT_BORDER;x--;
|
|
} else if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = LEFT_BORDER;y--;
|
|
} else {
|
|
next_border = TOP_BORDER;y++;
|
|
}
|
|
} else if (current_border == RIGHT_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = RIGHT_BORDER; y++;
|
|
} else if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = TOP_BORDER;y--;
|
|
} else {
|
|
next_border = LEFT_BORDER;x++;
|
|
}}
|
|
else if (current_border == RIGHT_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = TOP_BORDER;y++;
|
|
} else if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = RIGHT_BORDER;x--;
|
|
} else {
|
|
next_border = LEFT_BORDER;y--;
|
|
}
|
|
|
|
} else if (current_border == LEFT_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = TOP_BORDER;y--;
|
|
} else if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = LEFT_BORDER;x++;
|
|
} else {
|
|
next_border = RIGHT_BORDER;y++;
|
|
}
|
|
}
|
|
else if (current_border == LEFT_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = LEFT_BORDER;y--;
|
|
} else if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = TOP_BORDER;y++;
|
|
} else {
|
|
next_border = RIGHT_BORDER;x--;
|
|
}
|
|
}
|
|
}
|
|
else if (leftright == LEFT_HAND) { //podla pravidla lavej ruky
|
|
if (current_border == TOP_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = LEFT_BORDER;x--;
|
|
} else if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = RIGHT_BORDER;y++;
|
|
} else {
|
|
next_border = TOP_BORDER;y--;
|
|
}}
|
|
else if (current_border == TOP_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = RIGHT_BORDER;x++;
|
|
} else if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = LEFT_BORDER;y--;
|
|
} else {
|
|
next_border = TOP_BORDER;y++;
|
|
}
|
|
} else if (current_border == RIGHT_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = RIGHT_BORDER; y++;
|
|
} else if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = TOP_BORDER;y--;
|
|
} else {
|
|
next_border = LEFT_BORDER;x--;
|
|
}}
|
|
else if (current_border == RIGHT_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = TOP_BORDER;y++;
|
|
} else if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = RIGHT_BORDER;x++;
|
|
} else {
|
|
next_border = LEFT_BORDER;y--;
|
|
}
|
|
|
|
} else if (current_border == LEFT_BORDER && ((x + y) % 2 == 0)) {
|
|
if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = TOP_BORDER;y--;
|
|
} else if (!isborder(map, x, y, TOP_BORDER)) {
|
|
next_border = LEFT_BORDER;x--;
|
|
} else {
|
|
next_border = RIGHT_BORDER;y++;
|
|
}
|
|
}
|
|
else if (current_border == LEFT_BORDER && ((x + y) % 2 == 1)) {
|
|
if (!isborder(map, x, y, LEFT_BORDER)) {
|
|
next_border = LEFT_BORDER;y--;
|
|
} else if (!isborder(map, x, y, RIGHT_BORDER)) {
|
|
next_border = TOP_BORDER;y++;
|
|
} else {
|
|
next_border = RIGHT_BORDER;x++;
|
|
}
|
|
}
|
|
|
|
}
|
|
current_border = next_border;
|
|
|
|
}
|
|
}
|
|
int load_mapsize(int* mrow, int* mcol, const char* filename) // nacita velkost mapy zo suboru
|
|
{
|
|
FILE* file = fopen(filename, "r");
|
|
if (file == NULL)
|
|
{
|
|
fprintf(stderr,"Failed to open file\n");
|
|
return 1;
|
|
}
|
|
fscanf(file, "%d %d", mrow, mcol);
|
|
if(*mrow <= 0 || *mcol <= 0) //velkost mapy musi byt kladna, nulova je tiez chybna
|
|
{
|
|
return 2;
|
|
}
|
|
fclose(file);
|
|
return 0;
|
|
}
|
|
|
|
|
|
int main(int argc, char *argv[]) {
|
|
if (argc < 2)
|
|
{
|
|
fprintf(stderr,"Missing arguments\n");
|
|
return 1;
|
|
}
|
|
|
|
if (strcmp(argv[1], "--help") == 0)
|
|
{
|
|
printf(" Start program with these arguments:\n"
|
|
"\n"
|
|
"./maze --help\n"
|
|
"shows this guide\n"
|
|
"or\n"
|
|
"./maze --test soubor.txt\n"
|
|
"checks the validity of maze given in a file in second argument\n"
|
|
"nebo\n"
|
|
"./maze --rpath R C soubor.txt\n"
|
|
"finds path from input R-row,C-column in the maze to exit with right-hand rule,\n"
|
|
"nebo\n"
|
|
"./maze --lpath R C soubor.txt\n"
|
|
"finds path from input R-row,C-column in the maze to exit with left-hand rule,\n");
|
|
}
|
|
else if (strcmp(argv[1], "--test") == 0)
|
|
{
|
|
if (argc < 3)
|
|
{
|
|
fprintf(stderr,"missing name of file\n");
|
|
return 1;
|
|
}
|
|
// nacitanie velkosti mapy
|
|
int* mrows;
|
|
int* mcols;
|
|
mrows = malloc(sizeof(int));
|
|
mcols = malloc(sizeof(int));
|
|
|
|
int err = load_mapsize(mrows,mcols, argv[2]);
|
|
if(err == 1)
|
|
{
|
|
free(mrows);
|
|
free(mcols);
|
|
return 1;
|
|
}
|
|
else if(err == 2)
|
|
{
|
|
printf("Invalid\n");
|
|
free(mrows);
|
|
free(mcols);
|
|
return 0;
|
|
}
|
|
//koniec nacitania velkosti mapy
|
|
|
|
Map* map = init_map(*mrows, *mcols);
|
|
free(mrows);
|
|
free(mcols);
|
|
load_map(map, argv[2]);
|
|
bool valid = validate_map(map);
|
|
if (valid)
|
|
{
|
|
printf("Valid\n");
|
|
}
|
|
else
|
|
{
|
|
printf("Invalid\n");
|
|
}
|
|
free_map(map);
|
|
|
|
}
|
|
else if (strcmp(argv[1], "--rpath") == 0)
|
|
{
|
|
if (argc < 4) {
|
|
fprintf(stderr,"Missing arguments\n");
|
|
return 1;
|
|
}
|
|
int r = atoi(argv[2]);
|
|
int c = atoi(argv[3]);
|
|
|
|
//nacitannie velkosti mapy
|
|
int* mrows;
|
|
int* mcols;
|
|
mrows = malloc(sizeof(int));
|
|
mcols = malloc(sizeof(int));
|
|
|
|
int err = load_mapsize(mrows,mcols, argv[4]);
|
|
if(err == 1)
|
|
{
|
|
free(mrows);
|
|
free(mcols);
|
|
return 1;
|
|
}
|
|
else if(err == 2)
|
|
{
|
|
printf("Invalid\n");
|
|
free(mrows);
|
|
free(mcols);
|
|
return 0;
|
|
}
|
|
//koniec nacitania veloksti mapy
|
|
|
|
Map* map = init_map(*mrows, *mcols);
|
|
free(mrows);
|
|
free(mcols);
|
|
|
|
load_map(map, argv[4]);
|
|
if (r < 1 || r > map->rows || c < 1 || c > map->cols)
|
|
{
|
|
fprintf(stderr,"Wrong input coordinates\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
|
|
bool valid = validate_map(map);
|
|
if (!valid)
|
|
{
|
|
printf("Invalid\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
int sborder = start_border(map, r-1, c-1, RIGHT_HAND);
|
|
if (sborder == -1)
|
|
{
|
|
fprintf(stderr, "Invalid start border\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
else
|
|
{
|
|
find_path(map, r - 1, c - 1, RIGHT_HAND, sborder);
|
|
}
|
|
|
|
free_map(map);
|
|
|
|
}
|
|
else if (strcmp(argv[1], "--lpath") == 0)
|
|
{
|
|
|
|
if (argc < 4)
|
|
{
|
|
fprintf(stderr,"Missing arguments\n");
|
|
return 1;
|
|
}
|
|
int r =atoi(argv[2]);
|
|
int c =atoi(argv[3]);
|
|
|
|
//nacitanie velksoti mapy
|
|
int* mrows;
|
|
int* mcols;
|
|
mrows = malloc(sizeof(int));
|
|
mcols = malloc(sizeof(int));
|
|
|
|
int err = load_mapsize(mrows,mcols, argv[4]);
|
|
if(err == 1)
|
|
{
|
|
free(mrows);
|
|
free(mcols);
|
|
return 1;
|
|
}
|
|
else if(err == 2)
|
|
{
|
|
printf("Invalid\n");
|
|
free(mrows);
|
|
free(mcols);
|
|
return 0;
|
|
}
|
|
//koniec nacitania velkosti mapy
|
|
|
|
Map* map = init_map(*mrows, *mcols);
|
|
free(mrows);
|
|
free(mcols);
|
|
|
|
load_map(map, argv[4]);
|
|
if (r < 1 || r > map->rows || c < 1 || c > map->cols)
|
|
{
|
|
fprintf(stderr,"Wrong input coordinates\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
|
|
bool valid = validate_map(map);
|
|
if (!valid)
|
|
{
|
|
printf("Invalid\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
|
|
int sborder = start_border(map, r-1, c-1, LEFT_HAND);
|
|
if (sborder == -1)
|
|
{
|
|
fprintf(stderr, "Invalid start border\n");
|
|
free_map(map);
|
|
return 1;
|
|
}
|
|
else
|
|
{
|
|
find_path(map, r - 1, c - 1, LEFT_HAND, sborder);
|
|
}
|
|
free_map(map);
|
|
}
|
|
return 0;
|
|
}
|