NOIP学习小站一、走迷宫
问题：迷宫是一个正方形，边长为 \(n(2 \le n \le 400)\)，迷宫中的小格子（一共 \(n^2\) 个）有些能走通（标记 1），有些是墙壁（标记 0）。输入迷宫边长 \(n\) 和迷宫内部情况（\(n\) 行 \(n\) 列1、0整数），计算从迷宫左上角出发，到达右下角，最少需要走多少步？
分析：这里要求解最少步数，优先考虑使用宽度优先搜索。直接套用BFS的框架，参考程序如下：
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 400;
//用结构体表示坐标
struct Point{
int x,y;
Point(){}
Point(int x,int y){
this->x = x;
this->y = y;
}
};
int n;
int space[MAX+1][MAX+1]; //记录迷宫内部情况
int dist[MAX+1][MAX+1]; //记录到每一点的最小步数
int dirs[4][2] = {
{-1,0}, //向上走:x-1,y不变
{0,1}, //向右走:x不变,y+1
{1,0}, //向下走:x+1,y不变
{0,-1} //向左走:x不变,y-1
};
queue<Point> Q;
void bfs(){
Q.push(Point(1,1));
dist[1][1] = 0;
while(!Q.empty()){
Point p = Q.front();
Q.pop();
if(p.x==n && p.y==n) return; //到达终点，提前结束
int d = dist[p.x][p.y]; //走到(p.x,p.y)的步数
//枚举考查4个方向的移动情况
for(int i=0;i<4;i++){
int nx = p.x+dirs[i][0];
int ny = p.y+dirs[i][1];
//在迷宫内、能走通、并且没有搜索过
if(nx>=1 && nx<=n && ny>=1 && ny<=n && space[nx][ny] && dist[nx][ny]==-1){
dist[nx][ny] = d+1; //从(p.x,p.y)走来，步数+1
Q.push(Point(nx,ny));
}
}
}
}
int main()
{
cin>>n;
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++){
cin>>space[x][y];
dist[x][y] = -1; //每点最小步数初始化成特殊值-1
}
bfs();
if(dist[n][n]==-1) cout<<"No"<<endl;
else cout<<dist[n][n]<<endl;
return 0;
}可以测试下面的输入样例：
4 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1
4 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 1
二、P1135 奇怪的电梯
分析：从 A 楼开始，按一次按钮，可以上楼或者下楼，到达某个楼层，在这个楼层又可以按一次按钮，到达下一个楼层，…，同样的方式扩展下去，这是明显的广度优先搜索过程。在搜索的过程中记录下到达每个楼层按按钮的次数。需要注意的是，搜索到 C 楼层，如果 C 楼层前面已经被搜索过，此时不能继续搜索（这一次搜索到 C 楼层按按钮的次数肯定大于前面搜索过程中已经记录的值）。参考代码如下：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 200;
int n,A,B;
int K[MAX+1]; //每个楼层上写的数字
int ans[MAX+1]; //到达每个楼层至少按按钮次数
queue<int> Q;
void bfs(){
Q.push(A); //起点楼层入队
ans[A] = 0; //起点不需要按按钮，次数为0
while(!Q.empty()){
int floor = Q.front(); //考虑队首楼层
Q.pop();
if(floor==B) return; //到达目的楼层，提前结束搜索
int d = ans[floor]; //到达楼层按按钮次数
for(int f=-1;f<=1;f+=2){ //f依次取值-1和1，枚举下楼和上楼
int next = floor+f*K[floor]; //到达next楼层
//next在[1,n]范围内，并且next楼层之前没有被搜索过
if(next>=1 && next<=n && ans[next]==-1){
ans[next] = d+1; //按按钮次数+1
Q.push(next);
}
}
}
}
int main()
{
memset(ans,-1,sizeof(ans));
cin>>n>>A>>B;
for(int i=1;i<=n;i++) cin>>K[i];
bfs();
cout<<ans[B]<<endl;
return 0;
}三、细胞问题
问题：提供 \(n\) 行 \(n\) 列的全部为 1 或 0 的数据，0 表示细胞壁（4 个边界也是细胞壁），1 表示是细胞内部。如果均为细胞内部的两点联通（上下或者左右方向相邻），那么这两点属于同一个细胞。统计一共有多少个细胞，最大的细胞的规模（有几个点）。
分析：使用广度优先搜索依次搜索每一个非细胞壁的点，每一次会搜出来一个新的细胞，可以将搜出来的细胞的每个点打上编号。可知广搜一个非细胞壁的点时需要先判断这个点没有被打上编号才搜索。在搜索的过程中统计细胞数量和每个细胞的规模。
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 400;
//用结构体表示坐标
struct Point{
int x,y;
Point(){}
Point(int x,int y){
this->x = x;
this->y = y;
}
};
int n;
int space[MAX+2][MAX+2]; //记录内部情况（多开了1个，真正数据被0包围）
int cell[MAX+2][MAX+2]; //记录每一点的细胞编号
int cnt = 0,ans = 0; //细胞数量和最大细胞规模
int dirs[4][2] = {
{-1,0}, //向上移动:x-1,y不变
{0,1}, //向右移动:x不变,y+1
{1,0}, //向下移动:x+1,y不变
{0,-1} //向左移动:x不变,y-1
};
queue<Point> Q;
void bfs(int x,int y){
cnt++; //细胞数量+1
int total = 1; //记录本次搜索到的属于同一个细胞的点数
Q.push(Point(x,y));
cell[x][y] = cnt; //(x,y)处打上标记cnt（属于第cnt个细胞）
while(!Q.empty()){
Point p = Q.front();
Q.pop();
//枚举考查4个方向的移动情况
for(int i=0;i<4;i++){
int nx = p.x+dirs[i][0];
int ny = p.y+dirs[i][1];
//不是细胞壁、没有被标记过
if(space[nx][ny] && !cell[nx][ny]){
cell[nx][ny] = cnt; //这一点所属细胞编号也是cnt
total++; //细胞点数+1
Q.push(Point(nx,ny));
}
}
}
//计算细胞最大规模
if(total>ans) ans = total;
}
int main()
{
cin>>n;
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++)
cin>>space[x][y];
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++)
//不是细胞壁且没有被标记过，那么新找到一个细胞，从这一点开始广搜
if(space[x][y] && !cell[x][y]) bfs(x,y);
cout<<cnt<<" "<<ans<<endl;
return 0;
}可以测试下面的输入样例：
6 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1
6 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1
四、家庭问题
【问题描述】：有 \(n\) 个人，编号依次为 1,2,3,…,\(n\)，另外还知道存在 \(k\) 个关系。一个关系的表达为二元组 \((α,β)\) 形式，表示 \(α\)、\(β\) 为同一个家庭的一员。给出 \(n\)、\(k\) 以及 \(k\) 个关系，求出其中一共有多少个家庭，最大的家庭有多少人？
例如：\(n=6,k=3\)，三个关系为 \((1,2)\)、\((1,3)\)、\((4,5)\)。可知 6 个人分别属于三个家庭，\(\{1,2,3\}\) 为一个家庭，\(\{4,5\}\) 为一个家庭，\(\{6\}\) 为一个家庭，第一个家庭人数最多，最大家庭人数是 3。
【输入格式】：第一行是用一个空格隔开的两个正整数 \(n,k\)，接下来有 \(k\) 行，每行是用一个空格隔开的两个正整数表示一个关系。\(1 \le n \le 100\)。
【输出格式】：两个用一个空格隔开的整数，分别表示家庭数和最大家庭人数。
【输入样例】
6 3 1 2 1 3 4 5
【输出样例】
3 3
分析：这个问题和上面的细胞问题没有本质区别。枚举每一个人，如果发现他没有被搜索过，那么就对他展开广搜。对编号为 \(p\) 的人广搜过程中要寻找出所有与 \(p\) 有关系的人，为了能够方便找出这些人，可以开一个二维数组 edge 来表示任意两人之间的关系，输入每个关系 \((a,b)\) 时将这个数组元素 edge[a][b]=edge[b][a]=1;。这样处理后就能很好查找出与某个人有关系的所有人。
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 100;
int n;
int edge[MAX+1][MAX+1]; //表示任意两人是否属于同一个家庭
int ans[MAX+1]; //标记每个人所属家庭编号
queue<int> Q;
//搜索与编号p的人是同一个家庭的所有人，返回人数
int bfs(int p){
Q.push(p);
int total = 1;
while(!Q.empty()){
int f = Q.front();
Q.pop();
for(int i=1;i<=n;i++){ //考查所有人
if(i!=f && edge[f][i] && !ans[i]){
ans[i] = ans[f]; //同一个家庭
total++;
Q.push(i);
}
}
}
return total;
}
int main()
{
int k,a,b,maxCnt=0;
cin>>n>>k;
while(k--){
cin>>a>>b;
edge[a][b] = edge[b][a] = 1;
}
int cnt = 0;
for(int i=1;i<=n;i++){
//没有被标记过，找到一个新家庭的成员，展开搜索
if(ans[i]==0){
ans[i] = ++cnt;
maxCnt = max(maxCnt,bfs(i));
}
}
cout<<cnt<<" "<<maxCnt<<endl;
return 0;
}