HDU_3647
一开始不知道暴力搜就能过，后来看别人的题解说直接暴搜加回溯，于是自己也就直接写了个回溯，基本都是写好一段之后直接不停地cpoy、改参数，所以导致代码比较搓……
#include<stdio.h> #include<string.h> int N, M; char a[15]; void init() { for(int i = 0; i < 10; i ++) scanf("%s", a + i); } int dfs(int cur, int *H) { if(cur == 10) return 1; int i, h[40]; memcpy(h, H, sizeof(h)); if(a[cur] == 'I') { for(i = 0; i <= M - 4; i ++) if(h[i] < N && h[i] == h[i + 1] && h[i] == h[i + 2] && h[i] == h[i + 3]) { ++ h[i], ++ h[i + 1], ++ h[i + 2], ++ h[i + 3]; if(dfs(cur + 1, h)) return 1; -- h[i], -- h[i + 1], -- h[i + 2], -- h[i + 3]; } for(i = 0; i < M; i ++) if(h[i] + 4 <= N) { h[i] += 4; if(dfs(cur + 1, h)) return 1; h[i] -= 4; } } else if(a[cur] == 'J') { for(i = 0; i <= M - 3; i ++) if(h[i] + 2 <= N && h[i] == h[i + 1] && h[i] == h[i + 2]) { h[i] += 2, ++ h[i + 1], ++ h[i + 2]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i + 1], -- h[i + 2]; } for(i = 1; i < M; i ++) if(h[i] + 3 <= N && h[i] == h[i - 1]) { h[i] += 3, ++ h[i - 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i - 1]; } for(i = 2; i < M; i ++) if(h[i] + 2 <= N && h[i] + 1 == h[i - 1] && h[i - 1] == h[i - 2]) { h[i] += 2, ++ h[i - 1], ++ h[i - 2]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i - 2]; } for(i = 0; i <= M - 2; i ++) if(h[i] + 3 <= N && h[i] + 2 == h[i + 1]) { h[i] += 3, ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i + 1]; } } else if(a[cur] == 'L') { for(i = 2; i < M; i ++) if(h[i] + 2 <= N && h[i] == h[i - 1] && h[i] == h[i - 2]) { h[i] += 2, ++ h[i - 1], ++ h[i - 2]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i - 2]; } for(i = 1; i < M; i ++) if(h[i] + 3 <= N && h[i] + 2 == h[i - 1]) { h[i] += 3, ++ h[i - 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i - 1]; } for(i = 0; i <= M - 3; i ++) if(h[i] + 2 <= N && h[i] + 1 == h[i + 1] && h[i + 1] == h[i + 2]) { h[i] += 2, ++ h[i + 1], ++ h[i + 2]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i + 1], -- h[i + 2]; } for(i = 0; i <= M - 2; i ++) if(h[i] + 3 <= N && h[i] == h[i + 1]) { h[i] += 3, ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i + 1]; } } else if(a[cur] == 'O') { for(i = 0; i <= M - 2; i ++) if(h[i] + 2 <= N && h[i] == h[i + 1]) { h[i] += 2, h[i + 1] += 2; if(dfs(cur + 1, h)) return 1; h[i] -= 2, h[i + 1] -= 2; } } else if(a[cur] == 'S') { for(i = 1; i <= M - 2; i ++) if(h[i] + 2 <= N && h[i] == h[i - 1] && h[i] + 1 == h[i + 1]) { h[i] += 2, ++ h[i - 1], ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i + 1]; } for(i = 1; i < M; i ++) if(h[i] + 3 <= N && h[i] + 1 == h[i - 1]) { h[i] += 2, h[i - 1] += 2; if(dfs(cur + 1, h)) return 1; h[i] -= 2, h[i - 1] -= 2; } } else if(a[cur] == 'T') { for(i = 1; i <= M - 2; i ++) if(h[i] + 2 <= N && h[i] == h[i - 1] && h[i] == h[i + 1]) { h[i] += 2, ++ h[i - 1], ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i + 1]; } for(i = 1; i < M; i ++) if(h[i] + 3 <= N && h[i] + 1 == h[i - 1]) { h[i] += 3, ++ h[i - 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i - 1]; } for(i = 1; i <= M - 2; i ++) if(h[i] + 2 <= N && h[i] + 1 == h[i - 1] && h[i - 1] == h[i + 1]) { h[i] += 2, ++ h[i - 1], ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i + 1]; } for(i = 0; i <= M - 2; i ++) if(h[i] + 3 <= N && h[i] + 1 == h[i + 1]) { h[i] += 3, ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 3, -- h[i + 1]; } } else if(a[cur] == 'Z') { for(i = 1; i <= M - 2; i ++) if(h[i] + 2 <= N && h[i] == h[i + 1] && h[i] + 1 == h[i - 1]) { h[i] += 2, ++ h[i - 1], ++ h[i + 1]; if(dfs(cur + 1, h)) return 1; h[i] -= 2, -- h[i - 1], -- h[i + 1]; } for(i = 0; i <= M - 2; i ++) if(h[i] + 3 <= N && h[i] + 1 == h[i + 1]) { h[i] += 2, h[i + 1] += 2; if(dfs(cur + 1, h)) return 1; h[i] -= 2, h[i + 1] -= 2; } } return 0; } void solve() { int h[40]; memset(h, 0, sizeof(h)); printf("%s\n", dfs(0, h) ? "Yes" : "No"); } int main() { while(scanf("%d%d", &M, &N), N) { init(); solve(); } return 0; }