1.长草

题目
链接：长草 - 蓝桥云课 (lanqiao.cn)
题目描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，

这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

输入描述

输入的第一行包含两个整数 n*,*m。

接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。

接下来包含一个整数 k。其中，2≤n,m≤1000，1≤k≤1000。

输出描述

输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

输入输出样例

示例

输入
```
4 5
.g...
.....
..g..
.....
2
```
输出
```
gggg.
gggg.
ggggg
.ggg.
```

第一次 AC 0%

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
int const N=1100;

int n,m,k;
char g[N][N];
int d[N][N];
queue<PII> q;

void bfs()
{
	int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		for(int i=0;i<4;i++)
		{
			int x=t.first+dx[i],y=t.second+dy[i];
			if(d[x][y]==-1&&x<=n&&x>=1&&y<=m&&y>=1&&g[x][y]=='.')
			{
				q.push({x,y});
        		g[x][y]='g';
				d[x][y]=d[t.first][t.second]+1;
				if(d[x][y]==k)
					return ;
			}
		}
	}
	
}

int main()
{
	scanf("%d%d",&n,&m);
	
	memset(d,-1,sizeof d);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>g[i][j];
			if(g[i][j]=='g')
			{
				q.push({i,j});
				d[i][j]=0;
			}
		}
			
			
	scanf("%d",&k);
	
	bfs();
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<g[i][j];
		}
		cout<<endl;
	}
	
	return 0;
}

题解

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
int const N=1100;

int n,m,k,cnt;
char g[N][N];
int d[N][N];
queue<PII> q;
int len;

void bfs()
{
	
	int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
	
	while(q.size()&&k>0)
	{
		auto t=q.front();
		q.pop();
		
		for(int i=0;i<4;i++)
		{
			int x=t.first+dx[i],y=t.second+dy[i];
			if(d[x][y]==-1&&x<=n&&x>=1&&y<=m&&y>=1&&g[x][y]=='.')
			{
				q.push({x,y});
       			 g[x][y]='g';
			}
		}
    len--;     //一个点向四周扩展完之后，len--，表示这层的一个点已经完成扩展 //这里是重点！！！
    if(len==0)  //len ==0 说明这层的点已经全部完成扩展，令 len 重新等于刚扩展过程中放进去点的个数（即q.size(),我们之前的点都已经pop掉了，所以现在队列里面的点都是新放进去，属于下一层的点），并且层数k--
    {
      k--;
      len=q.size();
    }
	}
	
}

int main()
{
	scanf("%d%d",&n,&m);
	
	memset(d,-1,sizeof d);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>g[i][j];
			if(g[i][j]=='g')
			{
				q.push({i,j});
			}
		}
	len=q.size();		//最开始计往里面放了几个元素 len=q.size( )
			
	scanf("%d",&k);
	
	bfs();
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<g[i][j];
		}
		cout<<endl;
	}
	
	return 0;
}

反思
第一次的扩展层数不正确，代码没有实现成功；

题解中的记录扩展层数的方式：
- 最开始计往里面放了几个元素 len=q.size( )
- 一个点向四周扩展完之后，len–，表示这层的一个点已经完成扩展
- len ==0 说明这层的点已经全部完成扩展，令 len 重新等于刚扩展过程中放进去点的个数（即q.size(),我们之前的点都已经pop掉了，所以现在队列里面的点都是新放进去，属于下一层的点），并且层数k–

2.分考场

题目

链接：分考场 - 蓝桥云课 (lanqiao.cn)
n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求最少需要分几个考场才能满足条件。

输入描述

第一行，一个整数 n (1≤n≤100)，表示参加考试的人数。

第二行，一个整数 m，表示接下来有 m 行数据。

以下 m 行每行的格式为：两个整数 a*,b，用空格分开 ( 1≤a,b≤*n )表示第 a 个人与第 b 个人认识。

输出描述

输出一行一个整数，表示最少分几个考场。

输入输出样例

示例

输入
```
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
```
输出
```
4
```

第一次 AC 0%

#include<bits/stdc++.h>
using namespace std;

const int N=110;

int n,m,ans;
int p[N],s[N];

int find(int x)
{
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}

void add(int a,int b)
{
	s[b]+=s[a];
	ans=max(ans,s[b]);
	p[b]=find(p[a]);
}

int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
		s[i]=1;
	}
	
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	
	cout<<ans;
	
	return 0;
 }

想错了，这题长得真像并查集，a和b认识，b和c认识，但是a和b不一定认识

经过思考，我的思路：

先把n个数放在一个房间里面，a,b 认识，把其中一个从他们房间里面移出去；

移到隔壁房间，隔壁房间有认识的人，往下轮，直到找到没有认识的人房间，如果都不行，就新建一个房间 ans++

怎么实现呢

题解

#include<bits/stdc++.h>
using namespace std;

const int N=110;

int n,m;
bool g[N][N];  //矩阵数组：两个人认识为1，不认识为 0
vector<int>q[N];  //定义一个二维空间数组
int ans=0x3f3f3f3f;  //定义最后需要的房间

bool check(int id,int p)  //判断 p 这个考场，能不能放 id 这个人
{
	for(int j=0;j<q[p].size();j++)  //q[p].size() 表示考场的人数，精髓
	{
		if(g[id][q[p][j]])
			return false;
	}
	return true;
} 

void dfs(int id,int cnt)
{
	if(cnt>=ans)  //剪枝：一定不是最小的结果，回溯
		return;
	if(id==n+1)  // 所有人 都遍历了，回溯
	{
		ans=min(ans,cnt);  
		return;
	}
	
	for(int p=1;p<=cnt;p++)  //遍历每一个考场 
	{
		if(check(id,p)) //考场里没有熟人 
		{
			q[p].push_back(id);  //id放在 p这个考场里面
			dfs(id+1,cnt);  //放下一个 学生
			q[p].pop_back();   //恢复现场
		} 
	}
	
	if(cnt<n)  //经过上面的遍历每一个考场，没有 dfs ，说明没有考场可以放 id，so开一个新的考场
	{
		q[cnt+1].push_back(id);  //cnt+1
		dfs(id+1,cnt+1);  
		q[cnt+1].pop_back();   //回复现场
	}
	
}

int main()
{
	cin>>n>>m;
	
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		if(a!=b)
			g[a][b]=1,g[b][a]=1;
	}
	
	dfs(1,0);  //编号为 1，房间数号 0 
	
	cout<<ans; 
	
	return 0;
}

反思
怎么实现呢？我想了用邻接表，但是没有实现出来

题解中的vector二维数组真是妙

vector 二维数组：
- vector<int> q[m] 表示可以往 q[1]，q[2] 里面放一个数组，
  
  q[2][3] 表示 q[2]这个数组的第 3个元素，根据上面题中理解更透彻
  
  而且还可以使用 q[2].size() 就很方便
审题，避免整个思路方向性出现错误，dfs 会使用成并查集，老生常谈