http://www.zybbs.org/JudgeOnline/problem.php?id=1102
八中題目描述太DT了……還是看這里：
http://main.edu.pl/en/archive/oi/14/grz
水題不解釋……（我頹廢了）
bfs記錄一下高度相同的聯(lián)通塊，然后暴力枚舉聯(lián)通塊的周?chē)心居斜人€高（矮）的……完了……
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int px[8]={-1,-1,0,1,1,1,0,-1};
const int py[8]={0,1,1,1,0,-1,-1,-1};
int map[1001][1001],x[1000001],y[1000001],n,valleys,ridges;
bool vis[1001][1001];
bool check(int pos,char sym){
for(int k=1;k<=pos;k++)
for(int i=0;i<8;i++){
int xx=x[k]+px[i],yy=y[k]+py[i];
if(!(xx>0&&xx<=n&&yy>0&&yy<=n)) continue;
if((sym=='v'&&map[xx][yy]<map[x[k]][y[k]])||(sym=='r'&&map[xx][yy]>map[x[k]][y[k]])) return false;
}
return true;
}
void bfs(int posx,int posy){
int head=1,tail=0,xx,yy;
x[++tail]=posx,y[tail]=posy;
while(head<=tail){
for(int i=0;i<8;i++){
xx=x[head]+px[i],yy=y[head]+py[i];
if(!(xx>0&&xx<=n&&yy>0&&yy<=n&&map[xx][yy]==map[posx][posy]&&!vis[xx][yy])) continue;
vis[xx][yy]=true;
x[++tail]=xx,y[tail]=yy;
}
head++;
}
if(check(tail,'v')) valleys++;
if(check(tail,'r')) ridges++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) scanf("%d",&map[i][j]);
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!vis[i][j]) bfs(i,j);
printf("%d %d\n",ridges,valleys);
return 0;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
