这个题目用tarjan找联通块,缩点,然后统计出入度为0的点理论上是可行的,但问题是会暴栈。考虑到这个题目的特殊性,可以直接用一次bfs找到数字相同且联通的块,这就是一个联通块,然后缩点,统计出入度即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=1e3+9;
int a[maxn][maxn];
int con;
int ss[maxn*maxn],in[maxn*maxn],out[maxn*maxn];
int n,m;
struct
{
int t,s;
}que[maxn*maxn];
bool text[maxn*maxn];
void bfs()
{
con=0;
memset(text,0,sizeof(text));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!text[i*m+j])
{
int front=1,end=0;
que[++end].t=i;
que[end].s=j;
text[i*m+j]=1;
while(front<=end)
{
int t=que[front].t,s=que[front++].s;
for(int p=-1;p<=1;p++)
for(int q=-1;q<=1;q++)
if(fabs(p)+fabs(q)==1&&t+p>=1&&t+p<=n&&s+q>=1&&s+q<=m)
if(a[t][s]==a[t+p][s+q])
if(!text[(t+p)*m+s+q])
{
text[(t+p)*m+s+q]=1;
que[++end].t=t+p;
que[end].s=s+q;
}
}
con++;
for(int i=1;i<=end;i++)
{
ss[que[i].t*m+que[i].s]=con;
}
}
} int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d",&m,&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
bfs();
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int p=-1;p<=1;p++)
for(int q=-1;q<=1;q++)
if(fabs(p)+fabs(q)==1&&i+p>=1&&i+p<=n&&j+q>=1&&j+q<=m)
if(a[i][j]>=a[i+p][j+q])
if(ss[(i+p)*m+j+q]!=ss[i*m+j])
{
in[ss[(i+p)*m+j+q]]++;
out[ss[i*m+j]]++;
}
int ansin=0,ansout=0,ans;
for(int i=1;i<=con;i++)
{
if(in[i]==0)
ansin++;
if(out[i]==0)
ansout++;
}
ans=max(ansin,ansout);
if(con<=1)
printf("0\n");
else
printf("%d\n",ans);
}
return 0;
}
poj 2375 Cow Ski Area bfs的更多相关文章
-
POJ 2375 Cow Ski Area(强连通)
POJ 2375 Cow Ski Area id=2375" target="_blank" style="">题目链接 题意:给定一个滑雪场, ...
-
POJ 2375 Cow Ski Area
Cow Ski Area Time Limit: 1000ms Memory Limit: 65536KB This problem will be judged on PKU. Original I ...
-
POJ 2375 Cow Ski Area (强连通分量)
题目地址:POJ 2375 对每一个点向与之相邻并h小于该点的点加有向边. 然后强连通缩点.问题就转化成了最少加几条边使得图为强连通图,取入度为0和出度为0的点数的较大者就可以.注意,当强连通分量仅仅 ...
-
POJ 2375 Cow Ski Area[连通分量]
题目链接:http://poj.org/problem?id=2375题目大意:一片滑雪场,奶牛只能向相邻的并且不高于他当前高度的地方走.想加上缆车是的奶牛能从低的地方走向高的地方,求最少加的缆车数, ...
-
POJ 2375 Cow Ski Area【tarjan】
题目大意:一个W*L的山,每个山有个高度,当且仅当一个山不比它相邻(有公共边的格子)的山矮时能够滑过去,现在可以装化学电梯来无视山的高度滑雪,问最少装多少电梯使得任意两点都可到达 思路:最后一句话已经 ...
-
POJ2375 Cow Ski Area (强连通)(缩点)
Cow Ski Area Time Limit: 1000MS Memory Limit: 65536K Total Sub ...
-
D - Cow Ski Area
Description Farmer John's cousin, Farmer Ron, who lives in the mountains of Colorado, has recently t ...
-
[USACO2004][poj2375]Cow Ski Area(在特殊图上用floodfill代替强联通算法)
http://poj.org/problem?id=2375 题意:一个500*500的矩形,每个格子都有一个高度,不能从高度低的格子滑到高度高的格子(但相等高度可以滑),已知可以在2个相邻格子上加桥 ...
-
POJ 2251 Dungeon Master --- 三维BFS(用BFS求最短路)
POJ 2251 题目大意: 给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径,移动方向可以是上,下,左,右,前,后,六个方向,每移动一次就耗费一分钟,要求输出最快的走出时间.不同L层 ...
随机推荐
-
Unity3D ShaderLab 漫反射卷积光照模型
Unity3D ShaderLab 漫反射卷积光照模型 漫反射卷积[Diffuse convolution]是一个模糊立方体的过程,它保留了立方图的整体光照强度,只模糊了细节. 这种效果在我们要活得一 ...
-
安装 android sdk 不能更新问题
1 要更改host 文件 2在Android SDK Manager的Tool->Option中按照如下修改
-
DebugView图文教程
Debug信息捕获软件. 可以很方便的捕获系统实时输出的Debug信息,并保存为日志文件.可以远程捕获服务器上的Debug信息. 比较方便开发人员在系统发布前监控一些系统流程和异常,甚至在系统不大的情 ...
-
Performance Optimization (2)
DesktopGood performance is critical to the success of many games. Below are some simple guidelines f ...
-
读书笔记:java并发
java中主要的同步机制是关键字synchronized,它提供一种独占锁,但是 同步这个术语还包括validate类型的变量,显示锁(Explicit Lock)以及原子变量. -------显示锁 ...
-
java 中间String分类
String a = "aaa"; 用这样的方式的时候java首先在内存中寻找"aaa"字符串.假设有.就把aaa的地址给它 假设没有则创建 String a ...
-
WPR003N变成尸体的后记
这是一个很悲哀的标题,尽管本来不想说还是打算写出来. 应小便的要求本文不加任何字体变化,不设置玄关来等大家破解,只是很自然的把悲剧和大家分享一下. 自上回2019 Valentine's Day 圣地 ...
-
消息队列中间件(三)Kafka 入门指南
Kafka 来源 Kafka的前身是由LinkedIn开源的一款产品,2011年初开始开源,加入了 Apache 基金会,2012年从 Apache Incubator 毕业变成了 Apache * ...
-
使用DNSPod解析Freenom域名
注册Freenom域名 Freenom官网:http://www.freenom.com Freenom提供的*域名包括:tk,ml,ga,cf,gq 申请流程: 注册用户后登陆,然后查询并选择一个 ...
-
大数据处理算法--Bloom Filter布隆过滤
1. Bloom-Filter算法简介 Bloom-Filter,即布隆过滤器,1970年由Bloom中提出.它可以用于检索一个元素是否在一个集合中. Bloom Filter(BF)是一种空间效率很 ...