#include <stdio.h>
#include <cstring>
#define MAX_N	20


int N, M;
char board[MAX_N][MAX_N + 1];
bool points[MAX_N + 1][MAX_N + 1];
bool states[MAX_N + 1][MAX_N + 1][4];


enum Dir
{
	Left = 0,
	Right,
	Up,
	Down
};

typedef bool (*FUNC)(int r, int c, int& r2, int& c2);
FUNC funcs[4];


int oppdir(int dir)
{
	if (dir == Left) return Right;
	if (dir == Right) return Left;
	if (dir == Up) return Down;
	return Up;
}


bool up(int r, int c, int& r2, int& c2)
{
	if (r <= 0) return false;
	if (c <= 0 || c >= M) return false;
	if (board[r - 1][c - 1] == board[r - 1][c]) return false;
	r2 = r - 1;
	c2 = c;
	return true;
}


bool down(int r, int c, int& r2, int& c2)
{
	if (r >= N) return false;
	if (c <= 0 || c >= M) return false;
	if (board[r][c - 1] == board[r][c]) return false;
	r2 = r + 1;
	c2 = c;
	return true;
}


bool left(int r, int c, int& r2, int& c2)
{
	if (c <= 0) return false;
	if (r <= 0 || r >= N) return false;
	if (board[r - 1][c - 1] == board[r][c - 1]) return false;
	r2 = r;
	c2 = c - 1;
	return true;
}


bool right(int r, int c, int& r2, int& c2)
{
	if (c >= M) return false;
	if (r <= 0 || r >= N) return false;
	if (board[r - 1][c] == board[r][c]) return false;
	r2 = r;
	c2 = c + 1;
	return true;
}


bool cut(int r, int c, int dir, bool turn)
{
	if (states[r][c][dir]) return false;

	int r2, c2;
	if (funcs[dir](r, c, r2, c2)) {
		if (points[r2][c2]) {
			states[r2][c2][oppdir(dir)] = true;
			states[r][c][dir] = true;
			points[r][c] = true;
			//printf("%d %d\n", r, c);
			return true;
		}
		if (cut(r2, c2, dir, turn)) {
			states[r2][c2][oppdir(dir)] = true;
			states[r][c][dir] = true;
			points[r][c] = true;
			//printf("%d %d\n", r, c);
			return true;
		}
	}

	if (turn) return false;

	if (dir == Up || dir == Down) {
		if (cut(r, c, Left, true)) {
			return true;
		}
		if (cut(r, c, Right, true)) {
			return true;
		}
	}
	else {
		if (cut(r, c, Up, true)) {
			return true;
		}
		if (cut(r, c, Down, true)) {
			return true;
		}
	}
	return false;
}


int calc()
{
	for (int i = 0; i <= M; ++i) {
		points[0][i] = true;
		points[N][i] = true;
	}
	for (int i = 0; i <= N; ++i) {
		points[i][0] = true;
		points[i][M] = true;
	}

	int res = 1;
	while (true) {
		bool flag = false;

		//printf("cut %d\n", res);

		for (int i = 0; i <= N && !flag; ++i) {
			for (int j = 0; j <= M && !flag; ++j) {
				if (!points[i][j]) continue;

				for (int k = 0; k < 4; ++k) {
					if (cut(i, j, k, false)) {
						flag = true;
						break;
					}
				}
			}
		}

		if (flag) {
			++res;
		}
		else {
			break;
		}
	}

	return res;
}


int main()
{
	funcs[Up] = up;
	funcs[Down] = down;
	funcs[Left] = left;
	funcs[Right] = right;

	scanf_s("%d %d", &N, &M);
	while (N < 1 || N > MAX_N || M < 1 || M > MAX_N) printf("...");

	for (int i = 0; i < N; ++i) {
		scanf_s("%s", board[i], MAX_N + 1);
	}

	printf("%d\n", calc());
	return 0;
}

• Re:暴力搜索可切割的路径 (3406) cavatina2016 2019-09-12 21:29:35