705 - Slash Maze

本文主要是介绍705 - Slash Maze，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：705 - Slash Maze

题目大意：给一个斜线迷宫，求这个迷宫是否有环，最长环的长度。

解题思路：将斜线放大三倍，用数组来储存。这样的话就不需要八个方向遍历，只需要上下左右四个方向就可以了。然后如果有遍历到数组边界的就可以认定不是环了。

#include<stdio.h>
#include<string.h>const int N = 250;
char str[N];
int visit[N][N], map[N][N];
int w, h, t = 0, flag, cnt;int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};void change(int n) {for(int i = 0; i < w; i++)if(str[i] == '\\') {map[3 * n][3 * i] = 1;map[3 * n + 1][3 * i + 1] = 1;map[3 * n + 2][3 * i + 2] = 1;}else if(str[i] == '/') {map[3 * n][3 * i + 2] = 1;map[3 * n + 1][3 * i + 1] = 1;map[3 * n + 2][ 3 * i] = 1;}
}void dfs(int x, int y) {cnt++;visit[x][y] = 1;int i, x1, y1;for( i = 0; i < 4; i++) {x1 = x + dir[i][0];y1 = y + dir[i][1];if(x1 < 0 || x1 >= 3 * h || y1 < 0 || y1 >= 3 * w)continue;if(map[x1][y1] || visit[x1][y1])continue;if(x1 == 0 || x1 == 3 * h - 1 || y1 == 0 || y1 == 3 * w -1)flag = 1;dfs(x1, y1);}}int main() {while(scanf("%d%d%*c", &w, &h) , w || h) {t++;memset(map, 0, sizeof(map));memset(visit, 0, sizeof(visit));int i, j;for(i = 0; i < h; i++) {scanf("%s", str);change(i);}int circle_num = 0, max = 0;for(i = 1; i < 3*h - 1; i++)for(j = 1; j < 3*w - 1; j++)if(!map[i][j]  && !visit[i][j]) {flag = 0;cnt = 0;dfs(i, j);if(!flag) {circle_num++;if(cnt > max)max = cnt;}}printf("Maze #%d:\n", t);if(circle_num) printf("%d Cycles; the longest has length %d.\n\n", circle_num, max / 3);elseprintf("There are no cycles.\n\n");}return 0;
}

这篇关于705 - Slash Maze的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---