NOI科目校 信息学知识点测评-图论专题【51nod】 游记

比赛地址:Link

A 颜色块

1.0 秒 131,072.0 KB 100 分
一张 \(m\times n\) 的图片,每个点有一个颜色,相同颜色的点连在一起(上下左右四连通)属于同一个颜色块,问这张图片共有多少个颜色块。数据保证单个颜色块的点数量不超过 \(10^5\)。

输入

第一行:2个数\(n\),\(m\),中间用空格分隔,表示地图的大小(\(1 <= m, n <= 1000\))。
后面\(n\)行:每行\(m\)个字符,对应图片中的点的颜色编号\(c\)。(\(0 <= c <= 9\))。

输出

输出一个数,对应颜色块的数量

数据范围

\(1 <= m, n <= 1000\)

输入样例

5 5
11122
33112
31113
22113
21111

输出样例

5

样例解释

整个图中,有1个颜色为1的色块,2个颜色为2的色块,2个颜色为3的色块,因此共有5个色块。

通过记录

唰唰唰!秒杀!
毫无任何问题。

代码

#include<bits/stdc++.h>
using namespace std;
int mp[1005][1005];//存地图
bool v[1005][1005];//visited
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//四个方向
int m,n,ans=0;//ans=颜色块个数
void dfs(int x,int y){
	v[x][y]=1;//设置为标记过
	for(int i=0;i<4;i++){
		int dx=dir[i][0]+x,dy=dir[i][1]+y;
		if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!v[dx][dy]&&mp[dx][dy]==mp[x][y]) dfs(dx,dy);//符合条件
	}
}
int main(){
	char c;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			mp[i][j]=c-'0';//过于紧凑
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!v[i][j]){//每个都找一遍
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

B 冬奥会之积水问题

3.0 秒 131,072.0 KB 100 分
冬奥会赛场旁有一片正方形的洼地(长宽都为\(n\)),地形凹凸不平,洼地的四周是一圈排水池。有一天,下了很大的雨,洼地形成了积水,告诉你洼地的地形(\(n\times n\)块的高度),由你来计算,洼地的积水量。

例如:\(n = 4\)

3 4 5 6
4 1 2 7
5 1 2 8
6 7 8 9

因为四周都是排水池(边界上的水会通过排水池流走),最终只有橘色部分(内圈):

1 2
1 2

能够形成积水,积水高度由他们4周(绿色部分,外圈)的最低高度决定,这个高度是4(左上角0,0位置的3虽然小于4,但2个高度为4的方块已经形成了封闭的一圈),所以总的积水量是10。

输入

第一行:一个数n,表示洼地的大小(\(3 <= n <= 1000\))
后面n行:每行n个数,表示地形的高度h[i,j](\(0 <= h[i,j] <= 1000000\))。

输出

输出总的积水量。

输入样例

4
3 4 5 6
4 1 2 7
5 1 2 8
6 7 8 9

输出样例

10

思路

floodfill。
模拟海平面,每次增高都尝试流一遍。

悲惨de做题过程

最开始写了一发,惨拿46TAT
结果发现数组开小了/kx
然后卡在91卡了0.5h,终于发现写的时候没有处理0,顺序反了/kx
然后就100了/cy
这告诉了我们:一定要搞清楚you在干什么!!!!!

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mp[1005][1005];//地图
char vis[1005][1005];//是的,其实没啥用
struct three{
	int gao,x,y;//gao是高度
	bool operator <(three b) const{
		return gao>b.gao;
	}
};
priority_queue<three> q;
int n,m,mx=-1;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
signed main(){
	cin>>n;
	m=n;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){cin>>mp[i][j];mx=max(mx,mp[i][j]);}//mx存最大值
	for(int i=1;i<=m;i++){//处理四周
		q.push({mp[1][i],1,i});
		q.push({mp[n][i],n,i});
		vis[1][i]=2;
		vis[n][i]=2;
	}
	for(int i=1;i<=n;i++){
		q.push({mp[i][1],i,1});
		q.push({mp[i][m],i,m});
		vis[i][1]=2;
		vis[i][m]=2;
	}
	int ans=0,hpm=0;//hpm=海平面
	three now;
	while(!q.empty()&&hpm<=mx){
	//cout<<q.top().gao<<' '<<hpm<<endl;
		now=q.top();
		while(!q.empty()&&now.gao<=hpm){
			if(vis[now.x][now.y]==1){//这地方被淹了
				ans+=hpm-now.gao;
				//cout<<now.x<<","<<now.y<<":"<<now.gao<<" "<<hpm<<endl;
			}
			q.pop();
			vis[now.x][now.y]=2;
			for(int i=0;i<4;i++){
				int dx=now.x+dir[i][0];
				int dy=now.y+dir[i][1];
				if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){//查看四周
					vis[dx][dy]=1;
					q.push({mp[dx][dy],dx,dy});
				}
			}
			now=q.top();
		}
		hpm++;
	}
	cout<<ans<<endl;
	return 0;
}
/*以下是自造测试数据
4
0 2 100 0
10000 1 1 233
114 1 1 514
0 123 456 0
10
0 0 0 0 1 1 1 0 0 0
0 0 1 1 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 0 0 0
*/

(C没做出来不放了)

D 黏菌网络

1.0 秒 131,072.0 KB 100 分
小明正在研究黏菌(slime molds)。他有一张网状格栅,共\(10\times10\)个交点,每个交点上可以放置一些物体。他选择了其中3个交点,分别放置黏菌(M),糖(S),以及一块有毒物质(P),如下所示:

..........
..........
..........
..S.......
..........
.....P....
..........
..........
.....M....
..........

之后观察黏菌是否能避开毒物,并沿网格以最短路线找到糖。

小明希望你先帮忙算出黏菌到达糖之前至少要经过多少个空交点,以便他做实验记录。

输入

输入共10行,每行一个长度为10的字符串描述\(10\times10\)格栅中交点的情况。其中'.'表示空交点,'M'表示放置了黏菌,'S'表示放置了糖,'P'表示放置了毒物。保证输入数据中仅存在一组'M','S','P'。

输出

输出一个整数,表示黏菌经过的空交点的最小数量。

输入样例

..........
..........
..........
..S.......
..........
.....P....
..........
..........
.....M....
..........

输出样例

7

样例解释

..........
..........
..........
..S.......
..7.......
..6..P....
..5.......
..4.......
..321M....
..........

如上所示,黏菌需要经过至少7个空交点。

思路

这题放在T4也是绝了,是四道题里最简单的。
一个障碍,\(10\times 10\)大小,也不过如此。
直接爆搜。

通过记录

直接写。

code

#include<bits/stdc++.h>
using namespace std;
int n=10,sx,sy,ex,ey,ans=0;//startx,starty,endx,endy
bool mp[15][15];//map
bool v[15][15];//visited
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct th{//three
	int x,y,stp;
}now;
queue<th> q;
int bfs(){//bfs
	q.push({sx,sy,0});
	v[sx][sy]=1;
	while(!q.empty()){
		now=q.front();
		if(now.x==ex&&now.y==ey) return now.stp-1;//end
		q.pop();
		for(int i=0;i<4;i++){
			int dx=dir[i][0]+now.x,dy=dir[i][1]+now.y;
			if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&!mp[dx][dy]&&!v[dx][dy]){//ok
				v[dx][dy]=1;
				q.push({dx,dy,now.stp+1});
			} 
		}
	}
	return -1;
}
int main(){
	char c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>c;
			if(c=='M') sx=i,sy=j;//m
			else if(c=='S') ex=i,ey=j;//s
			else if(c=='P') mp[i][j]=1;//p
		}
	cout<<bfs()<<endl;
	return 0;
}
上一篇:nth-of-type的用法


下一篇:AcWing打卡-2014-岛