GRYZ 模 拟 赛 系 列 之 迷 宫(不就是个洪水)

时间:2024-08-06 15:05:14

-

迷 宫

(maze.cpp/c/pas)

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。

这个题,很水,但是,文件名多敲了一个空格所以0分;23333

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int hill[][];
bool mdzz[][];
int tot=; void dfs(int x,int y)
{
tot++;
mdzz[x][y]=;
if(x+<=n&&hill[x+][y]<=hill[x][y]&&mdzz[x+][y]==)
dfs(x+,y);
if(x->=&&hill[x-][y]<=hill[x][y]&&mdzz[x-][y]==)
dfs(x-,y);
if(y+<=m&&hill[x][y+]<=hill[x][y]&&mdzz[x][y+]==)
dfs(x,y+);
if(y->=&&hill[x][y-]<=hill[x][y]&&mdzz[x][y-]==)
dfs(x,y-);
else return;
} int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int sx,sy;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&hill[i][j]);
mdzz[i][j]=;
}
scanf("%d%d",&sx,&sy);
dfs(sx,sy);
printf("%d\n",m*n-tot);
int saber;
int qwq,qaq;
scanf("%d",&saber);
for(int i=;i<=saber;i++){
scanf("%d%d",&qwq,&qaq);
if(mdzz[qwq][qaq]==)printf("No\n");
else printf("Yes\n");
}
fclose(stdin);
fclose(stdout);
return ;
}