织梦网站栏目,小游戏免费入口,海南网站建设哪里有,别人网站 自己的二级域名WZK旅游
jzoj 1996
题目大意#xff1a;
给出一个nm的矩阵#xff0c;表示一个地方的高度#xff0c;高度相同且相邻#xff08;不算斜角#xff09;的算一块#xff0c;当整一块高度都大于周围时#xff0c;这是个山峰#xff0c;相反当高度都低于附近时是湖泊
给出一个n×m的矩阵表示一个地方的高度高度相同且相邻不算斜角的算一块当整一块高度都大于周围时这是个山峰相反当高度都低于附近时是湖泊现在问你有多少个湖泊和山坡
输入样例#1
2 2
1 2
1 1输入样例#2
3 4
1 3 2 6
1 2 2 7
3 2 2 5输出样例#1
1 1输出样例#2
1 3样例解释#1
唯一的湖泊高度为1存在的三个山峰高度分别为33和7。
数据范围
对于20%的数据 NM ≤ 10。 对于60%的数据 NM ≤ 100。 对于100%的数据 NM ≤ 1000高度信息 ≤ 1000000000。
解题思路
枚举每一块然后用bfs判断是否为湖泊或山坡即可
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,m,k,ans,sum,a[1500][1500],p[1500][1500];
const int dx[4]{1,0,-1,0};
const int dy[4]{0,1,0,-1};
struct rec
{int x,y;
};
int bfs(int x,int y)
{int xx,yy,num0;queuerecd;d.push((rec){x,y});while(!d.empty()){rec hd.front();d.pop();for (int i0;i4;i){xxh.xdx[i];yyh.ydy[i];if (xx0||xxn||yy0||yym) continue;//没出界if (a[xx][yy]a[h.x][h.y])if (!num||num1) num1;//没有记录过或相同else if (num2) num3;//违反了if (a[xx][yy]a[h.x][h.y])if (!num||num2) num2;//同上else if (num1) num3;if (!p[xx][yy]a[xx][yy]a[h.x][h.y])//没到过并{p[xx][yy]1;//记录d.push((rec){xx,yy});}}}return num;
}
int main()
{scanf(%d %d,n,m);for (int i1;in;i)for (int j1;jm;j)scanf(%d,a[i][j]);for (int i1;in;i)for (int j1;jm;j)if (!p[i][j]){p[i][j]1;kbfs(i,j);if (k1) ans;//湖泊else if (k2) sum;}printf(%d %d,ans,sum);return 0;
}
