NOJ——1559Jump to the Top of Mountain(简单暴力DFS+渣渣代码)
2024-08-29 20:15:13
[1559] Jump to the Top of Mountain
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
- Have you played a game named Minecraft?
In the game, there is a thing alloy you can not destroy, and its shape is a 1*1*1 area cube. I can only jump 1 meter at vertical height, it means I can jump from x meters height to y meters height when y is not more than x+1.Now, there is a rectangle field of m*n areas, each area is a positive interger X, X means the number of alloy in this area. You can only jump to four adjacent areas(up, down, left and right).
At the beginning, you are at out of the rectangle field, and the height is 0 out of the rectangle field.
Can you help me? I only want to know if I can jump to the peak of field? - 输入
- Input ends of EOF.
First line contains two positive integers m and n(3 <= m, n <= 100).
Then m lines, each line contains n intergers X(0 <= X <= 10000). - 输出
- If I can jump to the peak, output "YES", or output "NO".
- 样例输入
5 5
2 2 1 2 2
2 2 2 2 2
2 2 3 2 2
2 2 2 2 2
2 2 2 2 2
3 3
2 1 2
2 0 1
1 1 3
4 4
1 1 1 1
1 3 1 2
1 1 1 3
1 1 1 4
4 4
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13- 样例输出
YES
NO
YES
YES
基本没写过几道搜索。由于从边缘进入,枚举边缘所有格子进行搜索即可,如果认真读题肯定可以知道能向低处走...以为只能平地或高一格还赏了一个WA。蛋疼
代码非常搓+渣:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
int pos[110][110];
int vis[110][110];
int flag=0;
int tall;
int n,m;
void look(const int &x,const int &y,const int &pre)
{
if(x<0||y<0||x>=n||y>=m||vis[x][y]==1)//边界+是否访问过判断
return;
vis[x][y]=1;//标记访问
if(pos[x][y]-pre<=1)
{
if(pos[x][y]==tall)
{
flag=1;
puts("YES");
return;
}
look(x+1,y,pos[x][y]);
if(!flag)
look(x-1,y,pos[x][y]);
if(!flag)
look(x,y+1,pos[x][y]);
if(!flag)
look(x,y-1,pos[x][y]);
}
else
{
vis[x][y]=0;//路不通,不算访问过。
return;
}
}
int main(void)
{
int i,j;
while (~scanf("%d%d",&n,&m))
{
memset(pos,0,sizeof(pos));
tall=-1;flag=0;
for (i=0; i<n; i++)
{
for (j=0; j<m; j++)
{
scanf("%d",&pos[i][j]);
tall=max(tall,pos[i][j]);
}
}
if(tall==0)
{
puts("NO");
continue;
}
for (j=0; j<m; j++)
{
if(pos[0][j]==1)
{
memset(vis,0,sizeof(vis));
look(0,j,0);
}
if(flag)
break;
}
if(!flag)
{
for (j=0; j<m; j++)
{
if(pos[n-1][j]==1)
{
memset(vis,0,sizeof(vis));
look(n-1,j,0);
}
if(flag)
break;
}
}
if(!flag)
{
for (i=0; i<n; i++)
{
if(pos[i][0]==1)
{
memset(vis,0,sizeof(vis));
look(i,0,0);
}
if(flag)
break;
}
}
if(!flag)
{
for (i=0; i<n; i++)
{
if(pos[i][m-1]==1)
{
memset(vis,0,sizeof(vis));
look(i,m-1,0);
}
if(flag)
break;
}
}
if(!flag)
puts("NO");
}
return 0;
}
最新文章
- DEDECMS之七 如何实现文章推荐排行榜
- 关于Linux的内存(free -m)
- jquery中对动态生成的标签响应click事件(二)…与ajax交互使用
- Atitit.并发编程原理与概论 attilax总结
- 自定义Mvc5 Owin 验证
- (转)iOS被开发者遗忘在角落的NSException-其实它很强大
- 关于飞控下载时候出现avrdude: stk500_getsync(): not in sync: resp=0x00错误的解决方法
- python之安装
- LBA(逻辑区块地址)及PBA(物理区块地址)
- PHP实现插入排序算法
- Apriori算法-java
- vue分页组件
- 从图像中检测和识别表格,北航&微软提出新型数据集 TableBank
- Zabbix触发器支持的函数说明
- PLSQL导入Excel文件预览不到数据行问题
- 2018中国(深圳)IT领袖峰会马化腾演讲全文《数字中国的机遇与探索》
- LNMP笔记:阿里云32位 CentOS 5.4 配置 LNMP环境
- 使用RESTful风格整合springboot+mybatis
- wireshark: no interface can be used for capturing in this system
- node的socket.io的之事件篇
热门文章
- 字符编码ANSI和ASCII区别、Unicode和UTF-8区别
- 任务管理器 用 Ctrl + Shift + Esc 替换 Ctrl + Alt + Del
- python_89_configparser模块
- 【转】实用API大全
- macbook secureCRT终端中文乱码的问题
- Linux - which xxx - 查找执行的命令所在的路径
- ubuntu安装easygui模块
- ASP( VBScript ) 解析 JSON
- linux系统装载ELF过程
- POJ 1791 Parallelogram Counting(求平行四边形数量)