acm两道题？
第一题
Input

第一行两个整数M，N，代表矩形的行数和列数(1<=M<=100,1<=N<=100).
接下来的M行每行N个字符，仅由'.'和'x'组成。
其中'.'表示通路，'x'表示建筑。
每一步只能走上下左右四个方向的任意一个（如果该方向仍在给定地图内）。
第一行的第一个字符代表是北门，最后一行的最后一个字符代表是南门，这两个字符保证是'.'

Output

输出从北门到南门最快要走几步。
如果从北门不能走到南门，输出-1.

Sample Input
4 4
.xxx
...x
xx.x
xx..
Sample Output
6







第二题
某天我在想一道题，阿li在Q上给我来信息。
li:在干嘛？
我：在想一个题。
li：什么题？
我：用0和1两个数字组成一个n位的串，只要求数字1不能连续出现，问有多少种这样的n位串。
li：想多久了？
我：很久了。
li：。。。这难吗？
我：不难吗？
li：难吗？
……
好吧，由你决定难不难。

Input

多组输入，每组一行只有一个数字n，1<=n<=40.当n=0的时候，输入结束。数据保证结果不超过2的32次方。

Output

对应每组输入，每行输出一个数字s，其中s为n位串的总数。

Sample Input
1
2
0
Sample Output
2
3

[解决办法]
第一题，最简单的逐步扩散就可以，用图的最短路径搜索应该更好吧
第二题，递归