Mzc和男家丁的游戏

题目背景

mzc与djn的第二弹。

题目描述

mzc家很有钱(开玩笑),他家有n个男家丁(做过上一弹的都知道)。他把她们召集在了一起,他们决定玩捉迷藏。现在mzc要来寻找他的男家丁,大家一起来帮忙啊!

由于男家丁数目不多,再加上mzc大大的找人【laopo】水平很好,所以一次只需要找一个男家丁。

输入输出格式

输入格式:

第一行有两个数n,m,表示有n行m列供男家丁躲藏,

之后n行m列的矩阵,‘m‘表示mzc,‘d’表示男家丁,‘#’表示不能走,‘.‘表示空地。

输出格式:

一行,若有解:一个数sum,表示找到男家丁的最短移动次数。

若无解:输出“No Way!”。

输入输出样例

输入样例#1:

5 6
.#..#.
....#.
d.....
#####.
m.....

  

输出样例#1:

12

  

说明

3=<M,n<=2000

由于mzc大大十分着急,所以他只能等待1S。


好水啊。我不想写了,大大们直接看代码吧。>_<

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue> using namespace std; int n, m, sx, sy, ex, ey; char map[2003][2003]; bool vis[2003][2003], mark = false; struct node{int x, y, tot;}; queue<node> P; int dx[10] = {1, 0, -1, 0};
int dy[10] = {0, 1, 0, -1}; void bfs(node now) {
while(!P.empty()) {
now = P.front();
P.pop();
int x = now.x, y = now.y, tot = now.tot;
if(x == ex&&y == ey) {printf("%d\n", tot); mark = true; return ;}
for(int i=0; i<4; i++) {
int xx = dx[i]+x, yy = dy[i]+y;
if(xx <= n&&yy <= m&&xx > 0&&yy > 0&&map[xx][yy] != '#'&&!vis[xx][yy]) {
vis[xx][yy] = 1;
P.push((node) {xx, yy, tot+1});
}
}
}
} int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {cin>>map[i][j]; if(map[i][j] == 'm')sx = i, sy = j; if(map[i][j] == 'd')ex = i, ey = j;}
P.push((node) {sx, sy, 0});
vis[sx][sy] = 1;
bfs(P.front());
if(mark == false) printf("No Way!\n");
}

  

最新文章

  1. [LeetCode] H-Index 求H指数
  2. jQuery监听文本框值改变触发事件(propertychange)
  3. jQuery简单入门(二)
  4. C常用数据类型长度
  5. .Net性能优化时应该关注的数据
  6. 2:numpy---ndarray
  7. CentOS 7 上搭建LNMP环境
  8. NET Core 的 Views
  9. 201521123073 《Java程序设计》第8周学习总结
  10. ASP.NET Core 2.0 : 五.服务是如何加载并运行的, Kestrel、配置与环境
  11. visualSFM的使用方法
  12. NetBeans数据库笔记---三层架构
  13. 新人入坑Redis必会的吐血总结
  14. JavaScript中 this 的指向
  15. ECharts动态加载堆叠柱状图的实例
  16. jenkins使用Publish Over SSH中遇到的问题
  17. JVM内存模型(二)
  18. ORACLE 对一个表进行循环查数,再根据MO供给数量写入另一个新表
  19. 全球数据库--&gt;基金/管理产品--&gt;分类/行业平均
  20. 原生ajax与封装的ajax使用方法

热门文章

  1. BZOJ 3007 解救小云公主 二分答案+对偶图
  2. C++之:友元类
  3. OpenStack二三事(2)
  4. LeetCode 977. Squares of a Sorted Array (有序数组的平方)
  5. MapReduce04
  6. springAOP注解方式定义切入点报错error at ::0 can&#39;t find referenced pointcut
  7. Flume OG 与 Flume NG 的对比
  8. SQL Server 2008R2 Set IDENTITY_INSERT 表名 ON/OFF不能与insert into select 的语句一起执行?
  9. jq-文本框只能输入数字
  10. 04--Spring知识汇总