题目链接: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不能过,改了之后总算过了……)

 #include<cstdio>
int n,m,x,y,k;
struct Point{
int x,y;
}st,ed;
bool vis[][],flag;
int dx[]={,-,,};
int dy[]={,,-,};
bool is_in(int x,int y)
{
if(<=x && x<=n && <=y && y<=m) return ;
else return ;
}
bool judge(Point now)
{
Point next;
int cnt=;
for(int i=;i<;i++)
{
next.x=now.x+dx[i];
next.y=now.y+dy[i];
if(is_in(next.x,next.y) && vis[next.x][next.y]) cnt++;
}
if(cnt<=) return ;
else return ;
}
void dfs(Point now,int step)
{
if(flag) return;
if(now.x==ed.x && now.y==ed.y)
{
if(step>=k)
{
flag=;
vis[now.x][now.y]=;
}
return;
}
vis[now.x][now.y]=;
Point next;
for(int i=;i<;i++)
{
next.x=now.x+dx[i];
next.y=now.y+dy[i];
if(is_in(next.x,next.y)&&!vis[next.x][next.y]&&judge(next))
{
dfs(next,step+);
if(flag==) vis[next.x][next.y]=;
}
}
return;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&x,&y,&k);
st.x=, st.y=;
ed.x=x, ed.y=y;
flag=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(is_in(i,j)) vis[i][j]=;
else vis[i][j]=;
}
}
dfs(st,);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
printf("%c",(vis[i][j]==)?'.':'*');
}
printf("\n");
}
}

最新文章

  1. javascript实现原生ajax的方法
  2. 十五天精通WCF——第四天 你一定要明白的通信单元Message
  3. [git]fork+pull提交模式
  4. CCSpriteBatchNode的优化性能
  5. MVC 3 数据验证 Model Validation 详解
  6. JNI-使用RegisterNatives注册本地方法
  7. spring集成 log4j + slf4j
  8. 使用angularjs中ng-repeat的$even与$odd属性时的注意事项
  9. Serv-U无法连接到服务器127.0.0.1,端口43958 FTP服务器不能启动
  10. php 设计模式系列(一)
  11. [Lucas定理]【学习笔记】
  12. intellij idea 2017和Jprofiler 10的集成 报错问题
  13. odoo中各视图写法
  14. python学习笔记第一节
  15. ARM-start.s注释(2410Init.s)
  16. 6.8 lambda方法 6.9 枚举类
  17. 分布式监控系统Zabbix-3.0.3-完整安装记录(0)
  18. Error Code: 1175. You are using safe update mode and you tried to ......
  19. BZOJ1176:[Balkan2007]Mokia——题解
  20. 基于HTML5 FileSystem API的使用介绍(转)

热门文章

  1. NetBpm XML解读(5)
  2. 彻底删除weblogic域方法
  3. Yarn执行流程
  4. 利用Python爆破数据库备份文件
  5. 使用java连接数据库以后显示“ Establishing SSL connection without server&#39;s identity verification is not recommended”的警告如何解决
  6. 安装Alcatraz来管理Xcode插件的步骤和注意点
  7. (原)一句mpAudioPolicy-&gt;get_input引发的血案
  8. 【EF框架】使用params参数传值防止SQL注入报错处理
  9. Elasticsearch学习之多种查询方式
  10. 第二步 (仅供参考) sencha touch + PhoneGap(cordova 2.9 及其以下版本) 使用 adt eclipse进行打包