迷 宫

2018-06-18 04:04:40来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Visual Studio 默认保存为UTF8编码

下一篇:P2820 局域网