UVA_519
一开始裸的回溯，超时，后来想到了一些预判断，但还是超时了，看了UVA论坛上一个人发帖说预判断也没能saving他，于是我险些放弃了继续仔细想预判断的想法。
后来去W.C.的时候想到了更细化的预判断，出来之后又按这个思路继续想，于是得到了更多更细化的预判断，最终AC了，感觉细致的预判断是很强的剪枝呀。
我在预判断的时候主要考虑了下面几点：
①从全局角度讲，IO个数应该相等。
②所有的F的个数应是2*(M+N)，但这样还不够细致，我们仔细想一下不难得到下面这个更细致的条件，top和bottom中F的个数分别为M，left和right中F的个数分别为N。
③受讨论②时把四条边分开来看的启发，我们也可以想到上、下两个边缘上left和right的总IO个数应该相等，同理，左、右两个边缘上top和bottom的总IO个数也应该相等。
④根据拼图的规格，角上的F的个数应该是有限制的，不妨把这个限制的数量叫做limitk。比如如果N和M都为1，那么角应该有4个F，如果N和M有且仅有一个为1，那么角应该有3个F，如果N和M都不为1，那么角应该有2个F。上面的分析给了我们两点启发，第一，角上的F是最多的，因此若有一个拼图块的F的个数超过了limitk，显然无解，第二，如果满足F数为limitk的角的数量不符合相应的值的话，自然也无解。我的程序中并没有细化到每个角，只是看每个拼图块是否有limitk个F，实际上还可以根据F的位置再一步细化出是否各个角都有且仅有一个。
#include<stdio.h>
#include<string.h>
#define MAXD 40
#define MAXN 10
int N, M, T, top[MAXD], right[MAXD], bottom[MAXD], left[MAXD];
int D[MAXN][MAXN], R[MAXN][MAXN], A[MAXD];
char b[MAXN], *str = "IFO";
void init()
{
int i, j, k;
T = N * M;
for(i = 0; i < T; i ++)
{
scanf("%s", b);
top[i] = strchr(str, b[0]) - str - 1;
right[i] = strchr(str, b[1]) - str - 1;
bottom[i] = strchr(str, b[2]) - str - 1;
left[i] = strchr(str, b[3]) - str - 1;
}
}
int place(int cur, int x, int y)
{
if(x == 0 && top[cur] != 0)
return 0;
if(x != 0 && top[cur] + D[x - 1][y] != 0)
return 0;
if(y == M - 1 && right[cur] != 0)
return 0;
if(y != M - 1 && right[cur] == 0)
return 0;
if(x == N - 1 && bottom[cur] != 0)
return 0;
if(x != N - 1 && bottom[cur] == 0)
return 0;
if(y == 0 && left[cur] != 0)
return 0;
if(y != 0 && left[cur] + R[x][y - 1] != 0)
return 0;
return 1;
}
int dfs(int x, int y)
{
int i, j, k;
if(y == M)
++ x, y = 0;
if(x == N)
return 1;
for(i = 0; i < T; i ++)
if(!A[i] && place(i, x, y))
{
A[i] = 1;
D[x][y] = bottom[i], R[x][y] = right[i];
if(dfs(x, y + 1))
return 1;
A[i] = 0;
}
return 0;
}
int check()
{
int i, j, k, limitk, upcnt, downcnt, leftcnt, rightcnt;
int iototal, ioup, iodown, ioleft, ioright, num;
iototal = ioup = iodown = ioleft = ioright = 0;
upcnt = downcnt = leftcnt = rightcnt = num = 0;
if(N == 1 && M == 1)
limitk = 4;
else if(N == 1 || M == 1)
limitk = 3;
else
limitk = 2;
for(i = 0; i < T; i ++)
{
k = 0;
if(top[i] == 0)
++ upcnt, ++ k, ioup = ioup + (left[i] + right[i]);
if(right[i] == 0)
++ rightcnt, ++ k, ioright = ioright + (top[i] + bottom[i]);
if(bottom[i] == 0)
++ downcnt, ++ k, iodown = iodown + (left[i] + right[i]);
if(left[i] == 0)
++ leftcnt, ++ k, ioleft = ioleft + (top[i] + bottom[i]);
if(k > limitk)
return 0;
if(k == limitk)
++ num;
iototal = iototal + (top[i] + right[i] + bottom[i] + left[i]);
}
if(limitk == 2 && num != 4)
return 0;
if(limitk == 3 && num != 2)
return 0;
if(limitk == 4 && num != 1)
return 0;
if(upcnt != M || downcnt != M || leftcnt != N || rightcnt != N)
return 0;
if(iototal != 0 || ioup != 0 || ioright != 0 || iodown != 0 || ioleft != 0)
return 0;
return 1;
}
void solve()
{
if(!check())
{
printf("NO\n");
return ;
}
memset(A, 0, sizeof(A));
if(dfs(0, 0))
printf("YES\n");
else
printf("NO\n");
}
int main()
{
for(;;)
{
scanf("%d%d", &N, &M);
if(!N && !M)
break;
init();
solve();
}
return 0;
}