http://acm.pku.edu.cn/JudgeOnline/problem?id=1103
Код:
#include <stdio.h> #include <stdlib.h> char maze[80][80]; char already_been[80][80][2]; int main() { int cnt = 1; int size_x, size_y; int x, y, s; int start_x, start_y, start_s; int dir; int cycle_cnt, cycle_max_len; int length; while (1) { scanf("%d%d", &size_x, &size_y); if (size_x == 0) break; for (y = 0; y < size_y; y++) for (x = 0; x < size_x; x++) { scanf(" %c", &maze[x][y]); already_been[x][y][0] = 0; already_been[x][y][1] = 0; } cycle_cnt = 0; cycle_max_len = 0; for (start_x = 1; start_x < size_x; start_x++) for (start_y = 1; start_y < size_y; start_y++) for (start_s = 0; start_s < 2; start_s++) if (!already_been[start_x][start_y][start_s]) { x = start_x; y = start_y; s = start_s; dir = 0; length = 0; already_been[x][y][s] = 1; while (1) { if (dir == 1) { if (maze[x][y] == '/') dir = 0; else { if (s) y++; else x++; } } else { if (s == 1) { x--; dir = maze[x][y] == '/'; y += dir; } else { y--; dir = maze[x][y] == '/'; x += dir; } } s = !s; length++; if (x < s || y < !s || x >= size_x || y >= size_y) { break; } already_been[x][y][s] = 1; if (x == start_x && y == start_y && s == start_s) { cycle_cnt++; if (length > cycle_max_len) cycle_max_len = length; break; } } } printf("Maze #%d:\n", cnt++); if (cycle_cnt > 0) { printf("%d Cycles; the longest has length %d.\n\n", cycle_cnt, cycle_max_len); } else printf("There are no cycles.\n\n"); } return 0; }