1134.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1134 on 2006-01-16 at 21:09:35 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 80;
const int L_MAX = 160;

int DFS(int, int);
bool next(int&, int&);

bool vst[L_MAX][L_MAX];
char maze[MAX][MAX];
int w, h;

int main()
{
	int i, j, t;
	
	for(t = 1; scanf("%d %d", &w, &h) != EOF && w != 0; t++) {
		getchar();
		memset(vst, false, sizeof(vst));
		for(i = 0; i < h; i++) gets(maze[i]);
		int cycle = 0, cn = 0;
		h *= 2; w *= 2;
		for(i = 1; i <= w; i += 2) 
			DFS(0, i), DFS(h, i);
		for(i = 1; i <= h; i += 2) DFS(i, 0), DFS(i, w);
		for(i = 1; i < h; i++) {
			for(j = (i&1)+1; j < w; j += 2)
				if(!vst[i][j]) 
					cn++, cycle = max(cycle, DFS(i, j));
		}
		printf("Maze #%d:\n", t);
		if(cn == 0) printf("There are no cycles.\n\n");
		else printf("%d Cycles; the longest has length %d.\n\n", cn, cycle);
	}
	
	return 0;
}

int DFS(int x, int y)
{
	int n;
	for(n = 1; next(x, y); n++) ;
	return n;
}
bool next(int& x, int& y)
{
	vst[x][y] = true;
	int u = (x-1)/2, d = x/2, l = (y-1)/2, r = y/2;
	if(x > 0 && y > 0 && !vst[x-1][y-1] && maze[u][l] != '/') x--, y--;
	else if(x > 0 && y < w-1 && !vst[x-1][y+1] && maze[u][r] != '\\') x--, y++;
	else if(x < h-1 && y > 0 && !vst[x+1][y-1] && maze[d][l] != '\\') x++, y--;
	else if(x < h-1 && y < w-1 && !vst[x+1][y+1] && maze[d][r] != '/') x++, y++;
	else return false;
	return true;
}