1072.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 56 行

/*  This Code is Submitted by wywcgs for Problem 1072 on 2006-02-10 at 01:39:01 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const char *SHARP = "IFO";
const int MAX = 8;

int n, m, lay[MAX][MAX], kind[3][3][3][3];

bool find(int, int);

int main()
{
	int p[4], i, j;

	while(scanf("%d %d\n", &n, &m) != EOF && n != 0) {
		int all = n * m;
		memset(kind, 0, sizeof(kind));
		for(i = 0; i < all; i++) {
			char line[5]; gets(line);
			for(j = 0; j < 4; j++)
				for(p[j] = 0; SHARP[p[j]] != line[j]; p[j]++) ;
			kind[p[0]][p[1]][p[2]][p[3]]++;
		}
		printf("%s\n", find(0, m-1) ? "YES" : "NO");
	}
	
	return 0;
}

bool find(int r, int c)
{
	if(r == n) return true;
	else if(c == -1) return find(r+1, m-1);
	else {
		int u = (r == 0) ? 1 : 2-((lay[r-1][c]>>2)&3), ri = (c == m-1) ? 1 : 2-(lay[r][c+1]&3);
		int i, j;
		for(i = 0; i < 3; i++) {
			if(r != n-1 && i == 1) continue;
			else if(r == n-1 && i != 1) continue;
			for(j = 0; j < 3; j++) {
				if(c != 0 && j == 1) continue;
				else if(c == 0 && j != 1) continue;
				int &x = kind[u][ri][i][j];
				if(x > 0) {
					x--; lay[r][c] = (u<<6)|(ri<<4)|(i<<2)|j;
					if(find(r, c-1)) return true;
					x++;
				}
			}
		}
		return false;
	}
}