【POI 2007】 山峰和山谷
2024-08-31 07:38:11
【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=1102
【算法】
广度优先搜索
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
const int INF = 2e9;
const int dx[] = {,,-,,-,-,,};
const int dy[] = {-,,,,-,,-,}; int i,j,n,mn,mx,ans1,ans2;
int a[MAXN][MAXN];
bool visited[MAXN][MAXN]; inline bool valid(int x,int y)
{
return x >= && x <= n && y >= && y <= n;
}
inline void bfs(int x,int y)
{
int i,tx,ty;
queue< pair<int,int> > q;
pair<int,int> cur;
while (!q.empty()) q.pop();
q.push(make_pair(x,y));
while (!q.empty())
{
cur = q.front();
q.pop();
for (i = ; i < ; i++)
{
tx = cur.first + dx[i];
ty = cur.second + dy[i];
if (valid(tx,ty))
{
if (a[cur.first][cur.second] == a[tx][ty] && !visited[tx][ty])
{
q.push(make_pair(tx,ty));
visited[tx][ty] = true;
} else
{
mn = min(mn,a[tx][ty]);
mx = max(mx,a[tx][ty]);
}
}
}
}
} int main()
{ scanf("%d",&n);
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
scanf("%d",&a[i][j]);
}
}
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
if (!visited[i][j])
{
mx = mn = a[i][j];
visited[i][j] = true;
bfs(i,j);
if (mx <= a[i][j] && mn <= a[i][j]) ans1++;
if (mx >= a[i][j] && mn >= a[i][j]) ans2++;
}
}
}
printf("%d %d\n",ans1,ans2); return ; }
最新文章
- 客户关系管理系统-CRM源码
- 通过源码成功启动odoo 10.0
- vi 颜色配置
- Mysql 导入数据,推荐Source命令,太快了
- Android 客户端应用开发的架构
- pyenv
- apache开源项目 -- tez
- python使用mysqldb连接数据库操作方法示例详解
- STM32CubeMX GPIO的使用
- 我如何踏上IT路
- XML配置spring session jdbc实现session共享
- Unity3d之-使用BMFont制作美术字体
- WebAPI MVC Change Identity Default Table
- cocos2d 图片模糊
- Mysql优化-大数据量下的分页策略
- (27)session(设置值、取值、修改、删除)
- 安装Chrome浏览器
- SpringBoot-定制banner
- Java面试问题总结
- Solaris10 修改hostname