http://www.zybbs.org/JudgeOnline/problem.php?id=1102
八中題目描述太DT了……還是看這里:
http://main.edu.pl/en/archive/oi/14/grz
水題不解釋……(我頹廢了)
bfs記錄一下高度相同的聯通塊,然后暴力枚舉聯通塊的周圍有木有比他還高(矮)的……完了……
#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; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
