迷 宫
2018-06-18 04:04:40来源:未知 阅读 ()
Description
Karles 和朋友到迷宫玩耍,没想到遇上了 10000000 年一次的大洪水,好在 Karles 是一个喜
欢思考的人,他发现迷宫的地形和洪水有如下性质:
①迷宫可以被看做是一个 N*M 的矩形方阵,其中左上角坐标为(1,1),右下角坐标为(n,m),
每个格子(i,j)都有一个高度 h(i,j)。
②洪水从(sx,sy)开始,如果一个格子被洪水淹没,那这个格子四周比它低(或相同)的格子
也会被淹没。
现在 Karles 想请你帮忙算算,有多少个格子不会被淹没,以及 Karles 想问一下格子(x,y)是否
被淹没,如果被淹没的话就输出”Yes”,否则输出”No”。
Input
第一行包含两个整数 n,m。
以下 n 行,每行 m 个数,第 i 行第 j 个数表示格子高度 h(i,j)。
下面一行包含两个整数 sx,sy,表示最初被洪水淹没的格子。
下面一行包含一个整数 q,表示询问的数量。
最后 q 行每行包含两个整数 x,y,表示询问的格子。
Output
输出的第一行,为永远不会被淹没的格子的数量。
以下 q 行,为格子被淹没的情况,输出”Yes”或者”No”(不包含引号)
Example
maze.in maze.out
3 3
1 2 3
2 3 4
3 4 5
2 2
2
1 2
2 3
5
Yes
No
Hint
对于 10%的数据,(sx,sy)为迷宫内的最高点。
对于 30%的数据,1<=N,M<=5,q=1。
对于 60%的数据,1<=N,M<=100,q<=100。
对于 100%的数据,1<=N,M<=2000,q<=1000。
思路:很简单的棋盘型dfs问题,只要控制好边界,方向,高度,一步一步的搜索就可以、
最后的询问需要单独开一个vis数组
范围!范围!范围!
没看范围全部爆内存的代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<cstdlib> 7 using namespace std; 8 int xx[5]={-1,+1,0,0}; 9 int yy[5]={0,0,-1,+1}; 10 int a[10001][10001]; 11 int vis[10001][10001]; 12 int tot; 13 int n,m; 14 void dfs(int x,int y) 15 { 16 vis[x][y]=1; 17 for(int i=0;i<4;i++) 18 { 19 int h=a[x][y]; 20 if(a[x+xx[i]][y+yy[i]]<=h&&vis[x+xx[i]][y+yy[i]]==0&&x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=1&&y+yy[i]<=m) 21 { 22 tot--; 23 vis[x+xx[i]][y+yy[i]]=1; 24 dfs(x+xx[i],y+yy[i]); 25 } 26 } 27 } 28 int main() 29 { 30 freopen("maze.in","r",stdin); 31 freopen("maze.out","w",stdout); 32 scanf("%d%d",&n,&m); 33 tot=n*m; 34 for(int i=1;i<=n;i++) 35 { 36 for(int j=1;j<=m;j++) 37 { 38 scanf("%d",&a[i][j]); 39 } 40 } 41 int sx,sy; 42 scanf("%d%d",&sx,&sy); 43 dfs(sx,sy); 44 int q; 45 scanf("%d",&q); 46 printf("%d\n",tot-1); 47 for(int i=1;i<=q;i++) 48 { 49 int qx,qy; 50 scanf("%d%d",&qx,&qy); 51 if(vis[qx][qy]==1) 52 { 53 printf("Yes\n"); 54 } 55 else 56 { 57 printf("No\n"); 58 } 59 } 60 fclose(stdin); 61 fclose(stdout); 62 return 0; 63 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:P2820 局域网
- 朋友(翻转树边权值比赛)——依然是思维 2020-04-12
- 序列归并 2020-02-19
- 带毒的水 2019-08-16
- 蓝桥杯-历届试题 小朋友排队 (树状数组) 2018-12-04
- IEEE 二进制浮点数的表示 2018-12-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash