ECNU 3260

题目链接：http://acm.ecnu.edu.cn/problem/3260/

Time limit per test: 1.5 seconds

Time limit all tests: 10.0 seconds

Memory limit: 256 megabytes

袋鼠妈妈找不到她的孩子了。她的孩子被怪兽抓走了。

袋鼠妈妈现在在地图的左上角，她的孩子在地图第 x 行第 y 列的位置。怪兽想和袋鼠妈妈玩一个游戏：他不想让袋鼠妈妈过快地找到她的孩子。袋鼠妈妈每秒钟可以向上下左右四个方向跳一格（如果没有墙阻拦的话），怪兽就要在一些格子中造墙，从而完成一个迷宫，使得袋鼠妈妈能够找到她的孩子，但最快不能小于 k 秒。

请设计这样一个迷宫。

Input

第一行两个整数 n,m (1≤n,m≤8)，表示地图的总行数和总列数。

第二行三个整数 x,y,k (1≤x≤n,1≤y≤m,x+y>1)。

Output

输出一个地图，应正好 n 行 m 列。

用 . 表示空地，用 * 表示墙。袋鼠妈妈所在的位置和孩子所在的位置用 . 表示。

数据保证有解。

Examples

input

2 6
1 3 4

output

.*.***
......

根据网赛的题解：

由于数据范围很小，直接搜索就可以了。考虑 DFS，每一个要走的格子，周围最多只能有一格（其实就是走过来的那一格）是走过的。全部搜一遍就结束了。

所以我们就DFS走呗，除去保存下来的路径，其他都建成墙就行了。

当然，要注意的一点是：

（我刚开始也是step==k，然后特判了k<曼哈顿距离依然还有个case9不能过，改了之后总算过了……）

 1 #include<cstdio>
 2 int n,m,x,y,k;
 3 struct Point{
 4     int x,y;
 5 }st,ed;
 6 bool vis[10][10],flag;
 7 int dx[4]={0,-1,0,1};
 8 int dy[4]={1,0,-1,0};
 9 bool is_in(int x,int y)
10 {
11     if(1<=x && x<=n && 1<=y && y<=m) return 1;
12     else return 0;
13 }
14 bool judge(Point now)
15 {
16     Point next;
17     int cnt=0;
18     for(int i=0;i<4;i++)
19     {
20         next.x=now.x+dx[i];
21         next.y=now.y+dy[i];
22         if(is_in(next.x,next.y) && vis[next.x][next.y]) cnt++;
23     }
24     if(cnt<=1) return 1;
25     else return 0;
26 }
27 void dfs(Point now,int step)
28 {
29     if(flag) return;
30     if(now.x==ed.x && now.y==ed.y)
31     {
32         if(step>=k) 
33         {
34             flag=1;
35             vis[now.x][now.y]=1;
36         }
37         return;
38     }
39     vis[now.x][now.y]=1;
41     Point next;
42     for(int i=0;i<4;i++)
43     {
44         next.x=now.x+dx[i];
45         next.y=now.y+dy[i];
46         if(is_in(next.x,next.y)&&!vis[next.x][next.y]&&judge(next))
47         {
48             dfs(next,step+1);
49             if(flag==0) vis[next.x][next.y]=0;
50         }
51     }
52     return;
53 }
54 int main()
55 {
56     scanf("%d%d%d%d%d",&n,&m,&x,&y,&k);
57     st.x=1, st.y=1;
58     ed.x=x, ed.y=y;
59     flag=0;
60     for(int i=0;i<=9;i++)
61     {
62         for(int j=0;j<=9;j++)
63         {
64             if(is_in(i,j)) vis[i][j]=0;
65             else vis[i][j]=1;
66         }
67     }
69     dfs(st,0);
70     for(int i=1;i<=n;i++)
71     {
72         for(int j=1;j<=m;j++)
73         {
74             printf("%c",(vis[i][j]==1)?'.':'*');
75         }
76         printf("
");
77     }
78 }