学步园

这个题其实没有什么特别的技巧，就是直接DFS就行了，至于时间嘛，按一般的DFS都不会超时。

题目链接  http://acm.hdu.edu.cn/showproblem.php?pid=3647 这里还可以提交

这个题只要细心就没有多大的问题，要把所有的情况都考虑进去。

// 1007 mnlm 1.0<br /> #include<cstdio><br /> #include<cstdlib><br /> #include<cmath><br /> #include<cstring><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;<br /> int n, m;<br /> char s[10]; // 积木下降的类型<br /> int h[41]; // 储存现有状态，h[i]表示第i列的高度<br /> bool DFS(int k)<br /> {<br /> int i;<br /> if (k == 10)<br /> {<br /> return true;<br /> }<br /> switch (s[k])<br /> {<br /> case 'I':<br /> for (i = 0; i < n; i++)<br /> {<br /> if (h[i] + 4 <= m)<br /> {<br /> h[i] += 4;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i] -= 4;<br /> }<br /> if (i + 3 < n &&<br /> h[i] < m &&<br /> h[i] == h[i + 1] &&<br /> h[i + 1] == h[i + 2] &&<br /> h[i + 2] == h[i + 3])<br /> {<br /> h[i]++;<br /> h[i + 1]++;<br /> h[i + 2]++;<br /> h[i + 3]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 3]--;<br /> h[i + 2]--;<br /> h[i + 1]--;<br /> h[i]--;<br /> }<br /> }<br /> break;<br /> case 'L':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i]+ 3 <= m &&<br /> h[i] == h[i + 1])<br /> {<br /> h[i] += 3;<br /> h[i + 1]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1]--;<br /> h[i] -= 3;<br /> }<br /> if (h[i + 1] + 3 <= m &&<br /> h[i] == h[i + 1] + 2)<br /> {<br /> h[i]++;<br /> h[i + 1] += 3;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 3;<br /> h[i]--;<br /> }<br /> if (i + 2 < n)<br /> {<br /> if (h[i] + 2 <= m &&<br /> h[i] + 1 == h[i + 1] &&<br /> h[i + 1] == h[i + 2])<br /> {<br /> h[i] += 2;<br /> h[i + 1]++;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1]--;<br /> h[i] -= 2;<br /> }<br /> if (h[i + 2] + 2 <= m &&<br /> h[i] == h[i + 1] &&<br /> h[i + 1] == h[i + 2])<br /> {<br /> h[i]++;<br /> h[i + 1]++;<br /> h[i + 2] += 2;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2] -= 2;<br /> h[i + 1]--;<br /> h[i]--;<br /> }<br /> }<br /> }<br /> break;<br /> case 'J':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i + 1] + 3 <= m &&<br /> h[i] == h[i + 1])<br /> {<br /> h[i]++;<br /> h[i + 1] += 3;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 3;<br /> h[i]--;<br /> }<br /> if (h[i] + 3 <= m &&<br /> h[i] + 2 == h[i + 1])<br /> {<br /> h[i] += 3;<br /> h[i + 1]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1]--;<br /> h[i] -= 3;<br /> }<br /> if (i + 2 < n)<br /> {<br /> if (h[i] + 2 <= m &&<br /> h[i] == h[i + 1] &&<br /> h[i + 1] == h[i + 2])<br /> {<br /> h[i] += 2;<br /> h[i + 1]++;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1]--;<br /> h[i] -= 2;<br /> }<br /> if (h[i + 2] + 2 <= m &&<br /> h[i] == h[i + 1] &&<br /> h[i + 1] == h[i + 2] + 1)<br /> {<br /> h[i]++;<br /> h[i + 1]++;<br /> h[i + 2] += 2;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2] -= 2;<br /> h[i + 1]--;<br /> h[i]--;<br /> }<br /> }<br /> }<br /> break;<br /> case 'O':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i] + 2 <= m &&<br /> h[i] == h[i + 1])<br /> {<br /> h[i] += 2;<br /> h[i + 1] += 2;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 2;<br /> h[i] -= 2;<br /> }<br /> }<br /> break;<br /> case 'S':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i] + 2 <= m &&<br /> h[i] == h[i + 1] + 1)<br /> {<br /> h[i] += 2;<br /> h[i + 1] += 2;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 2;<br /> h[i] -= 2;<br /> }<br /> if (i + 2 < n &&<br /> h[i + 2] + 1 <= m &&<br /> h[i] == h[i + 1] &&<br /> h[i + 1] + 1 == h[i + 2])<br /> {<br /> h[i]++;<br /> h[i + 1] += 2;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1] -= 2;<br /> h[i]--;<br /> }<br /> }<br /> break;<br /> case 'T':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i] + 3 <= m &&<br /> h[i] + 1 == h[i + 1])<br /> {<br /> h[i] += 3;<br /> h[i + 1]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1]--;<br /> h[i] -= 3;<br /> }<br /> if (h[i + 1] + 3 <= m &&<br /> h[i] == h[i + 1] + 1)<br /> {<br /> h[i]++;<br /> h[i + 1] += 3;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 3;<br /> h[i]--;<br /> }<br /> if (i + 2 < n &&<br /> h[i + 1] + 2 <= m)<br /> {<br /> if (h[i] == h[i + 1] &&<br /> h[i + 1] == h[i + 2])<br /> {<br /> h[i]++;<br /> h[i + 1] += 2;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1] -= 2;<br /> h[i]--;<br /> }<br /> if (h[i] == h[i + 1] + 1 &&<br /> h[i + 1] + 1 == h[i + 2])<br /> {<br /> h[i]++;<br /> h[i + 1] += 2;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1] -= 2;<br /> h[i]--;<br /> }<br /> }<br /> }<br /> break;<br /> case 'Z':<br /> for (i = 0; i < n - 1; i++)<br /> {<br /> if (h[i + 1] + 2 <= m &&<br /> h[i] + 1 == h[i + 1])<br /> {<br /> h[i] += 2;<br /> h[i + 1] += 2;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 1] -= 2;<br /> h[i] -= 2;<br /> }<br /> if (i + 2 < n &&<br /> h[i] + 1 <= m &&<br /> h[i] == h[i + 1] + 1 &&<br /> h[i + 1] == h[i + 2])<br /> {<br /> h[i]++;<br /> h[i + 1] += 2;<br /> h[i + 2]++;<br /> if (DFS(k + 1))<br /> {<br /> return true;<br /> }<br /> h[i + 2]--;<br /> h[i + 1] -= 2;<br /> h[i]--;<br /> }<br /> }<br /> break;<br /> default :;<br /> }<br /> return false;<br /> }<br /> int main()<br /> {<br /> while (1)<br /> {<br /> scanf("%d%d", &n, &m);<br /> if (!n && !m)<br /> {<br /> break;<br /> }<br /> int i;<br /> for (i = 0; i < 10; i++)<br /> {<br /> scanf("%s", &s[i]);<br /> }<br /> memset(h, 0, sizeof(h));<br /> if (DFS(0))<br /> {<br /> printf("Yes/n");<br /> }<br /> else<br /> {<br /> printf("No/n");<br /> }<br /> }<br /> return 0;<br /> }<br />