uva-705-深搜

题意,就是根据斜线组成的迷宫,判断能够组成多少个闭环.

解法:

放大俩倍或者三倍

俩倍

\     ------->10

　　　　　　01

三倍

\　　------->100

　　　　　　 010

　　　　　　 001

然后深搜,有个问题,没有判断是否成环,它竟然过了,待证明----它到底对不对

#include<stdio.h>

#include<iostream>

#include<queue>

#include<memory.h>

using namespace std;

const int MAX = 80 * 3;

int maps[MAX][MAX];

int r, c;

void dfs(int x, int y, int tr, int tc, int* total, int* ok)

{

	*total = *total + 1;

	maps[x][y] = 1;

	if(x == 0 || x == (tr - 1) || y == 0 || y == (tc - 1))

		*ok = 0;

	if(x > 0 && maps[x - 1][y] == 0)

		dfs(x - 1, y, tr, tc, total, ok);

	if(y > 0 && maps[x][y - 1] == 0)

		dfs(x, y - 1, tr, tc, total, ok);

	if(x < (tr - 1) && maps[x + 1][y] == 0)

		dfs(x + 1, y, tr, tc, total, ok);

	if(y < (tc - 1) && maps[x][y + 1] == 0)

		dfs(x, y + 1, tr, tc, total, ok);

}

int main()

{

	freopen("d:\\1.txt", "r", stdin);

	int T = 1;

	while (cin >> c >> r)

	{

		if(r == 0 && c == 0)

			return 0;

		memset(maps, 0, sizeof(maps));

		char cc;

		for(int i = 0; i < r; i++)

		{

			for(int j = 0; j < c; j++)

			{

				cin >> cc;

				if(cc == '/')

				{

					maps[3 * i][3 * j + 2] = 1;

					maps[3 * i + 1][3 * j + 1] = 1;

					maps[3 * i + 2][3 * j] = 1;

				}

				else if(cc == '\\')

				{

					maps[3 * i][3 * j] = 1;

					maps[3 * i + 1][3 * j + 1] = 1;

					maps[3 * i + 2][3 * j + 2] = 1;

				}

			}

		}

		int mr = 3 * r;

		int mc = 3 * c;

		int t = 0;

		int max = 0;

		for(int i = 0; i < mr; i++)

			for(int j = 0; j < mc; j++)

			{

				if(maps[i][j] == 0)

				{

					int ok = 1;

					int total = 0;

					dfs(i, j, mr, mc, &total, &ok);

					if(ok)

					{

						max = max > total ? max : total;

						t++;

					}

				}

			}

		cout << "Maze #" << T << ":" << endl;

		if(t == 0)

			cout << "There are no cycles." << endl;

		else

			cout << t << " Cycles; the longest has length " << max / 3 << "."

					<< endl;

		cout << endl;

		T++;

	}

	return 0;

}