比赛地址：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;
}