SHOW:
|
|
- or go back to the newest paste.
1 | #include <stdio.h> | |
2 | #include <stdbool.h> | |
3 | #include <string.h> | |
4 | #include <ctype.h> | |
5 | #include <stdlib.h> | |
6 | ||
7 | #define strSize 1000 // число строк/столбцов | |
8 | #define upDown 4 | |
9 | #define left 1 | |
10 | #define right 2 | |
11 | ||
12 | // структура карты | |
13 | typedef struct { | |
14 | int rows; | |
15 | int cols; | |
16 | unsigned char *cells; | |
17 | } Map; | |
18 | ||
19 | struct prirustek { | |
20 | int dr; | |
21 | int ds; | |
22 | }; | |
23 | ||
24 | enum smery { vychod, sever, zapad, jih, POCET_SMERU }; | |
25 | ||
26 | struct prirustek d[POCET_SMERU] = { | |
27 | {0, +1}, // vychod (0) | |
28 | {-1, 0}, // sever (1) | |
29 | {0, -1}, // zapad (2) | |
30 | {+1, 0}, // jih (3) | |
31 | }; | |
32 | ||
33 | // является ли строка числом | |
34 | bool isCharNum(char *argument) { | |
35 | int len = strlen(argument); | |
36 | bool result = true; | |
37 | ||
38 | for (int i = 0; i < len; i++) { | |
39 | if (!isdigit(argument[i])) { | |
40 | result = false; | |
41 | } | |
42 | } | |
43 | return result; | |
44 | } | |
45 | ||
46 | // сколько слов в строке, без пробелов | |
47 | int wordsInStr(char *str) { | |
48 | int i; | |
49 | int words = 0; | |
50 | ||
51 | for (i = 0; i < strlen(str) - 1; i++) { | |
52 | if (str[i] == ' ' && str[i+1] != ' ') { | |
53 | words++; | |
54 | } | |
55 | ||
56 | if (str[0] != ' ' && i == 0) { | |
57 | words++; | |
58 | } | |
59 | } | |
60 | ||
61 | return words; | |
62 | } | |
63 | ||
64 | // является ли формат файла txt или нет | |
65 | bool fileTxt(char *fileName) { | |
66 | if ( | |
67 | (fileName[strlen(fileName) - 4] == '.') && | |
68 | (fileName[strlen(fileName) - 3] == 't') && | |
69 | (fileName[strlen(fileName) - 2] == 'x') && | |
70 | (fileName[strlen(fileName) - 1] == 't') | |
71 | ) | |
72 | { | |
73 | return true; | |
74 | } | |
75 | else | |
76 | { | |
77 | fprintf(stderr, "Error: file is not '.txt'"); | |
78 | return false; | |
79 | } | |
80 | } | |
81 | ||
82 | // получение значения из ячейки стуктуры | |
83 | char getCell(Map *map, int row, int col) { | |
84 | return map->cells[ row * map->cols + col ]; | |
85 | } | |
86 | ||
87 | // проверка границы сверху или снизу | |
88 | bool hasBorderTopOrBottom(char cell) { | |
89 | return cell == '4' || cell == '5' || cell == '6' || cell == '7'; | |
90 | } | |
91 | ||
92 | // проверка границы слева | |
93 | bool hasBorderLeft(char cell) { | |
94 | return cell == '1' || cell == '3' || cell == '5' || cell == '7'; | |
95 | } | |
96 | ||
97 | //проверка границы справа | |
98 | bool hasBorderRight(char cell) { | |
99 | return cell == '2' || cell == '3' || cell == '6' || cell == '7'; | |
100 | } | |
101 | ||
102 | // проверка конфликта двух рядом стоящих элементов по горизонтали | |
103 | bool hasHorizontalConflicts(char leftCell, char rightCell) { | |
104 | switch (rightCell){ | |
105 | case '1' : | |
106 | case '3' : | |
107 | case '5' : | |
108 | case '7' : return leftCell == '1' || leftCell == '4' || leftCell == '5' || leftCell == '0'; | |
109 | case '0' : | |
110 | case '2' : | |
111 | case '4' : | |
112 | case '6' : return leftCell == '2' || leftCell == '3' || leftCell == '6' || leftCell == '7'; | |
113 | } | |
114 | } | |
115 | ||
116 | // проверка конфликта двух рядом стоящих элементов по вертикали | |
117 | bool hasVerticalConflicts(char downCell, char upCell) { | |
118 | switch (downCell){ | |
119 | case '1' : | |
120 | case '2' : | |
121 | case '3' : | |
122 | case '0' : return upCell == '4' || upCell == '5' || upCell == '6' || upCell == '7'; | |
123 | case '4' : | |
124 | case '5' : | |
125 | case '6' : | |
126 | case '7' : return upCell == '1' || upCell == '2' || upCell == '3' || upCell == '0'; | |
127 | } | |
128 | } | |
129 | ||
130 | // проверка на конфликт значений элементов двух ячеек | |
131 | bool hasConflictCells(Map *map, int i, int j){ | |
132 | bool error = false; | |
133 | if (j > 0){ | |
134 | error = hasHorizontalConflicts(getCell(map, i, j-1), getCell(map, i, j)); | |
135 | ||
136 | } | |
137 | if (i > 0 && (i + j) % 2 == 0 && !error){ | |
138 | error = hasVerticalConflicts(getCell(map, i - 1, j), getCell(map, i, j)); | |
139 | } | |
140 | return error; | |
141 | } | |
142 | ||
143 | ||
144 | ||
145 | // проверка карты | |
146 | bool readAndTestMap(Map *map, char *fileName) | |
147 | { | |
148 | FILE *fp; | |
149 | fp = fopen(fileName, "r"); | |
150 | ||
151 | // проверка, что такой файл есть | |
152 | if (fp == NULL) { | |
153 | fprintf(stderr, "Can't open file '%s'\n", fileName); // не удалось открыть такой файл | |
154 | return false; | |
155 | } else { | |
156 | char str[strSize] = ""; | |
157 | // считываем первую строку из файла | |
158 | fgets(str, strSize, fp); | |
159 | ||
160 | // проверяем, что в строке только 2 слова | |
161 | if (wordsInStr(str) == 2) { | |
162 | char *firstword = strtok(str, " "); | |
163 | char *secondword = strtok(NULL, "\n"); | |
164 | ||
165 | // проверка, что считаные элементы являются цифрами | |
166 | if (isCharNum(firstword) && isCharNum(secondword)) { | |
167 | map->rows = atoi(firstword); // определяем количество строк | |
168 | map->cols = atoi(secondword); // определяем количество столбцов | |
169 | ||
170 | map->cells = malloc(map->rows * map->cols * sizeof(unsigned char) + 1); // выделяем память под структуру | |
171 | ||
172 | // начинаем считывать строки из файла | |
173 | for (int i = 0; i < map->rows; i++) { | |
174 | fgets(str, strSize, fp); | |
175 | ||
176 | // проверяем, что количество слов в строке соответствует количеству столбцов | |
177 | if (wordsInStr(str) != map->cols) { | |
178 | fprintf(stderr, "Invalid\n"); // не соответствует | |
179 | return false; | |
180 | } | |
181 | ||
182 | // меняем символ новой строки на символ конца строки | |
183 | if (str[strlen(str)-1] == '\n') { | |
184 | str[strlen(str)-1] = '\0'; | |
185 | } | |
186 | ||
187 | int len = strlen(str); | |
188 | ||
189 | firstword = strtok(str, " "); // дробим строку по пробелам | |
190 | ||
191 | for (int j = 0; j < map->cols || firstword != NULL; j++) { | |
192 | ||
193 | // проверка, что число однозначное | |
194 | if (firstword[1] != NULL) { | |
195 | fprintf(stderr, "Invalid\n"); // в числе более одного знака | |
196 | return false; | |
197 | } else { | |
198 | ||
199 | // проверка, что значения лежат в пределах от 0 до 7 | |
200 | if (firstword[0] >= '0' && firstword[0] <= '7') { | |
201 | char number = firstword[0]; | |
202 | // запись элемента в структуру | |
203 | map->cells[i*map->cols+j] = number; | |
204 | firstword = strtok(NULL, " "); // переход к новому слову | |
205 | } else { | |
206 | fprintf(stderr, "Invalid\n"); | |
207 | return false; | |
208 | } | |
209 | ||
210 | } | |
211 | ||
212 | } | |
213 | } | |
214 | // проверка, на соответствие массива количеству строк | |
215 | if (fgets(str, strSize, fp)) { | |
216 | fprintf(stderr, "Invalid\n"); | |
217 | return false; | |
218 | } | |
219 | ||
220 | bool isClose = true; // переменная для проверки на закрытость лабиринта | |
221 | ||
222 | // проверяем только нечетные позиции первой и последней строки на закрытость | |
223 | for (int j = 0; j < map->cols; j = j + 2) { | |
224 | if ( | |
225 | !hasBorderTopOrBottom(getCell(map, 0, j)) || | |
226 | !hasBorderTopOrBottom(getCell(map, map->rows - 1, j)) | |
227 | ) { | |
228 | isClose = false; // есть открытая граница | |
229 | ||
230 | } | |
231 | } | |
232 | ||
233 | // проверка на закрытость левой и правой границы массива | |
234 | for (int j = 0; j < map->rows; j = j + 1) { | |
235 | if ( | |
236 | !hasBorderLeft(getCell(map, j, 0)) || | |
237 | !hasBorderRight(getCell(map, j, map->cols - 1)) | |
238 | ) { | |
239 | isClose = false; // есть открытая границы | |
240 | ||
241 | } | |
242 | } | |
243 | ||
244 | // если лабиринт закрыт, сообщаем об этом | |
245 | if (isClose) { | |
246 | fprintf(stderr, "Invalid\n"); | |
247 | return false; | |
248 | } | |
249 | ||
250 | // проверка, что рядом стоящие числа не конфликтуют друг с другом | |
251 | for (int i = 0; i < map->rows; i++){ | |
252 | for (int j = 0; j < map->cols; j++){ | |
253 | if (hasConflictCells(map, i, j)){ | |
254 | fprintf(stderr, "Invalid\n"); | |
255 | return false; | |
256 | } | |
257 | ||
258 | } | |
259 | } | |
260 | ||
261 | } else { | |
262 | fprintf(stderr, "Invalid\n"); | |
263 | return false; | |
264 | } | |
265 | ||
266 | ||
267 | } | |
268 | } | |
269 | ||
270 | return true; | |
271 | } | |
272 | ||
273 | bool isborder(Map *map, int r, int c, int border) { | |
274 | bool levo, pravo, verchNiz; | |
275 | levo = (getCell(map, r, c) - '0') & left; | |
276 | pravo = (getCell(map, r, c) - '0') & right; | |
277 | verchNiz = (getCell(map, r, c) - '0') & upDown; | |
278 | switch(border) { | |
279 | case sever : | |
280 | case jih : return verchNiz; | |
281 | case vychod : return pravo; | |
282 | case zapad : return levo; | |
283 | ||
284 | } | |
285 | } | |
286 | ||
287 | int start_border(Map *map, int r, int c, int leftright) { | |
288 | int smer; | |
289 | // right hand | |
290 | if (leftright == 0) { | |
291 | if ((r + c) % 2 == 0) { | |
292 | if (c == 0 && !isborder(map, r, c, zapad)) { | |
293 | smer = vychod; | |
294 | } | |
295 | else if (c == map->cols - 1 && !isborder(map, r, c, vychod)) { | |
296 | smer = sever; | |
297 | } | |
298 | else if (r == 0 && !isborder(map, r, c, sever)) { | |
299 | smer = zapad; | |
300 | } | |
301 | else { | |
302 | fprintf(stderr, "Bad vstup\n"); | |
303 | return -1; | |
304 | } | |
305 | } | |
306 | else { | |
307 | if (c == 0 && !isborder(map, r, c, zapad)) { | |
308 | smer = jih; | |
309 | } | |
310 | else if (c == map->cols - 1 && !isborder(map, r, c, vychod)) { | |
311 | smer = zapad; | |
312 | } | |
313 | else if (r == map->rows -1 && !isborder(map, r, c, jih)) { | |
314 | smer = vychod; | |
315 | } | |
316 | else { | |
317 | fprintf(stderr, "Bad vstup\n"); | |
318 | return -1; | |
319 | } | |
320 | } | |
321 | } | |
322 | // left hand | |
323 | else { | |
324 | if ((r + c) % 2 == 0) { | |
325 | if (c == 0 && !isborder(map, r, c, zapad)) { | |
326 | smer = sever; | |
327 | } | |
328 | else if (c == map->cols - 1 && !isborder(map, r, c, vychod)) { | |
329 | smer = zapad; | |
330 | } | |
331 | else if (r == 0 && !isborder(map, r, c, sever)) { | |
332 | smer = vychod; | |
333 | } | |
334 | else { | |
335 | fprintf(stderr, "Bad vstup\n"); | |
336 | return -1; | |
337 | } | |
338 | } | |
339 | else { | |
340 | if (c == 0 && !isborder(map, r, c, zapad)) { | |
341 | smer = vychod; | |
342 | } | |
343 | else if (c == map->cols - 1 && !isborder(map, r, c, vychod)) { | |
344 | smer = jih; | |
345 | } | |
346 | else if (r == map->rows - 1 && !isborder(map, r, c, jih)) { | |
347 | smer = zapad; | |
348 | } | |
349 | else { | |
350 | fprintf(stderr, "Bad vstup\n"); | |
351 | - | void walkInLabirinthleft(Map *map, int row, int col, int hand, int smer) { |
351 | + | return -1; |
352 | } | |
353 | } | |
354 | ||
355 | } | |
356 | return smer; | |
357 | } | |
358 | ||
359 | ||
360 | void walkInLabirinthRight(Map *map, int row, int col, int hand, int smer) { | |
361 | ||
362 | while ((row < map->rows && col < map->cols) && (row >= 0 && col >= 0)) { | |
363 | while (isborder(map, row, col, smer)) { | |
364 | smer = (smer + 1) % POCET_SMERU; | |
365 | if ((row + col) % 2 == 0 && smer == jih) { | |
366 | smer = (smer + 1) % POCET_SMERU; | |
367 | } | |
368 | else if ((row + col) % 2 != 0 && smer == sever) { | |
369 | smer = (smer + 1) % POCET_SMERU; | |
370 | } | |
371 | } | |
372 | printf("%d,%d\n", row + 1, col + 1); | |
373 | row = row + d[smer].dr; | |
374 | col = col + d[smer].ds; | |
375 | ||
376 | if (((row + col) % 2 == 0 && smer == vychod) || ((row + col) % 2 != 0 && smer == zapad)){ | |
377 | } | |
378 | ||
379 | else { | |
380 | smer = (smer + 3) % POCET_SMERU; | |
381 | - | char *argv3 = "0"; |
381 | + | |
382 | - | char *argv1 = "--rpath"; |
382 | + | |
383 | - | char *argv2 = "0"; |
383 | + | |
384 | } | |
385 | ||
386 | void walkInLabirinthLeft(Map *map, int row, int col, int hand, int smer) { | |
387 | ||
388 | while ((row < map->rows && col < map->cols) && (row >= 0 && col >= 0)) { | |
389 | - | printf("--help - vypisuje napovedu\n"); |
389 | + | |
390 | smer = (smer + 3) % POCET_SMERU; | |
391 | if ((row + col) % 2 == 0 && smer == jih) { | |
392 | smer = (smer + 3) % POCET_SMERU; | |
393 | } | |
394 | else if ((row + col) % 2 != 0 && smer == sever) { | |
395 | smer = (smer + 3) % POCET_SMERU; | |
396 | } | |
397 | } | |
398 | printf("%d,%d\n", row + 1, col + 1); | |
399 | row = row + d[smer].dr; | |
400 | col = col + d[smer].ds; | |
401 | ||
402 | if (((row + col) % 2 == 0 && smer == zapad) || ((row + col) % 2 != 0 && smer == vychod)){ | |
403 | } | |
404 | ||
405 | else { | |
406 | smer = (smer + 1) % POCET_SMERU; | |
407 | } | |
408 | ||
409 | } | |
410 | } | |
411 | ||
412 | // int main(int argc, char *argv[]) { | |
413 | int main() { | |
414 | int argc = 5; | |
415 | ||
416 | - | int startRows = atoi(argv2); |
416 | + | char *argv2 = "3"; |
417 | - | int startCols = atoi(argv3); |
417 | + | char *argv3 = "7"; |
418 | char *argv1 = "--lpath"; | |
419 | - | if ((strcmp(argv1, "--rpath") == 0))// && (startRows > 0 && startRows <= map.rows) && (startCols > 0 && startCols <= map.cols)) |
419 | + | |
420 | char *argv4 = "bludiste.txt"; | |
421 | ||
422 | Map map; | |
423 | if (argc == 2 && (strcmp(argv1, "--help") == 0)) { | |
424 | printf("Napoveda!\nZadejte vstup, cislo radku a cislo sloupci!\nSpecialni komandy:\n"); | |
425 | printf("-- help - vypisuje napovedu\n"); | |
426 | printf("--test nazev_souboru.txt - zkontroluje, ze soubor dany druhym argumentem programu obsahuje radnou definici mapy bludiste\n"); | |
427 | - | else if ((strcmp(argv1, "--lpath") == 0) && (startRows > 0 && startRows <= map.rows) && (startCols > 0 && startCols <= map.cols)) |
427 | + | |
428 | printf("--lpath R C nazev_souboru.txt - hleda pruchod bludistem, zadanym z souboru txt, na vstupu na rádku R a sloupci C. Pruchod hleda pomoci pravidla leve ruky (leva ruka vzdy na zdi)\n"); | |
429 | printf("--shortest R C nazev_souboru.txt - hleda nejkratsi cestu z bludiste, zadanym z souboru txt, pri vstupu na radku R a sloupci C\n"); | |
430 | ||
431 | return 0; | |
432 | } | |
433 | ||
434 | else if (argc == 3 && strcmp(argv1, "--test") == 0 && fileTxt(argv2)) { | |
435 | if (readAndTestMap(&map, argv2)) { | |
436 | printf("Valid\n"); | |
437 | } else { | |
438 | printf("Invalid\n"); | |
439 | ||
440 | return 0; | |
441 | } | |
442 | } | |
443 | ||
444 | // основной цикл | |
445 | else if (argc == 5 && fileTxt(argv4)) | |
446 | { | |
447 | readAndTestMap(&map, argv4); | |
448 | int leftright; | |
449 | // правило правой руки | |
450 | if (isCharNum(argv2) && isCharNum(argv3)) | |
451 | { | |
452 | int startRows = atoi(argv2) - 1; | |
453 | int startCols = atoi(argv3) - 1; | |
454 | ||
455 | if ((strcmp(argv1, "--rpath") == 0) && (startRows >= 0 && startRows < map.rows) && (startCols >= 0 && startCols < map.cols)) | |
456 | { | |
457 | leftright = 0; // правая рука | |
458 | int smer = start_border(&map, startRows, startCols, leftright); | |
459 | walkInLabirinthRight(&map, startRows, startCols, leftright, smer); | |
460 | return 0; | |
461 | } | |
462 | // правило левой руки | |
463 | else if ((strcmp(argv1, "--lpath") == 0) && (startRows >= 0 && startRows < map.rows) && (startCols >= 0 && startCols < map.cols)) | |
464 | { | |
465 | leftright = 1; // левая рука | |
466 | int smer = start_border(&map, startRows, startCols, leftright); | |
467 | walkInLabirinthLeft(&map, startRows, startCols, leftright, smer); | |
468 | return 0; | |
469 | } | |
470 | /* самый короткий путь | |
471 | else if((strcmp(argv1, "--shortest") == 0) && (startRows > 0 && startRows <= map.rows) && (startCols > 0 && startCols <= map.cols)) | |
472 | { | |
473 | //leftright =1; | |
474 | return 0; | |
475 | }*/ | |
476 | else | |
477 | { | |
478 | fprintf(stderr, "Error: chybna komanda\nPro napovedu napiste --help\n"); | |
479 | return -1; | |
480 | } | |
481 | } | |
482 | else | |
483 | { | |
484 | fprintf(stderr, "Error: chybna komanda\nPro napovedu napiste --help\n"); | |
485 | return -1; | |
486 | } | |
487 | } | |
488 | else | |
489 | { | |
490 | fprintf(stderr, "Error: chybna komanda\nPro napovedu napiste --help\n"); | |
491 | return -1; | |
492 | } | |
493 | ||
494 | free(map.cells); | |
495 | return 0; | |
496 | } |