题意：输入n，m。表示有一个n*m的拼图。然后输入每一块拼图F代表平的。I代表凸的。O代表凹的。要求判断这个拼图能不能拼出来。。 思路：深搜。。不过要进行剪枝不然会超时。一格格去放拼图。放不了就进行回溯。

剪枝点：

1、由于边缘一定是平的。内部一定是凸凹结合的。所以判断F的数量等不等于2 * n * m，以及I的数量等不等于O的数量。如果不等于直接输入NO结束。

2、如果有一块拼图在一个位置上不能拼。那么下次遇到一样的拼图的时候直接跳过（这个剪枝我剪了以后直接就过了..欣慰）

#include<bits/stdc++.h>
using namespace std;

vector<string> upper, down, left, right;
bool visit[37];
int grid[6][6];
char block[10000][10000];
int n, m;
bool dfs(int x, int y) {
	if (grid[x][y] >= 0)
		return dfs(x, y + 1);
	if (y == m)
		return dfs(x + 1, 0);
	if (x == n)
		return 1;

	bool l = 0, r = 0, u = 0, d = 0;
	if (x == 0)
		u = 1;
	if (y == 0)
		l = 1;
	if (x == n - 1)
		d = 1;
	if (y == m - 1)
		r = 1;
	for (int i = 0; i < n * m; i++)
		if (visit[i] == 0) {
			if (u && block[i][0] != 'F' || l && block[i][3] != 'F' || d && block[i][2] != 'F' || r && block[i][1] != 'F')
				continue;
			if (x > 0 && block[i][0] == block[grid[x - 1][y]][2] || y > 0 && block[i][3] == block[grid[x][y - 1]][1])
				continue;
			visit[i] = 1;
			grid[x][y] = i;
			if (dfs(x, y + 1) == 1)
				return 1;
			visit[i] = 0;
			grid[x][y] = -1;
		}
	return 0;
}

int main() {
	while (cin >> n >> m && n) {
		string s;
		bool invalid = 0;
		memset(grid, -1, sizeof(grid));
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < n * m; i++) {
			cin >> block[i];
			int t = 0, po;
			for (int j = 0; j < 4; j++)
				if (block[i][j] == 'F')
					t++, po = j;
			if (t == 2) {
				if (block[i][0] == 'F' && block[i][3] == 'F') {
					if (grid[0][0] >= 0)
						invalid = 1;
					else
						grid[0][0] = i, visit[i] = 1;
				} else if (block[i][0] == 'F' && block[i][2] == 'F') {
					if (grid[0][m - 1] >= 0)
						invalid = 1;
					else
						grid[0][m - 1] = i, visit[i] = 1;
				} else if (block[i][1] == 'F' && block[i][3] == 'F') {
					if (grid[n - 1][0] >= 0)
						invalid = 1;
					else
						grid[n - 1][0] = i, visit[i] = 1;
				} else if (block[i][1] == 'F' && block[i][2] == 'F') {
					if (grid[n - 1][m - 1] >= 0)
						invalid = 1;
					else
						grid[n - 1][m - 1] = i, visit[i] = 1;
				} else
					invalid = 1;
			}


			memset(visit, 0, sizeof(visit));

		}
		
	}
	if (dfs(0, 0))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	return 0;
}