东莞建设网官方网站,2022最新永久地域网名,深圳十大甲级装饰公司,营销和运营的区别是什么作者#xff1a;指针不指南吗 专栏#xff1a;蓝桥杯倒计时冲刺 #x1f43e;马上就要蓝桥杯了#xff0c;最后的这几天尤为重要#xff0c;不可懈怠哦#x1f43e; 文章目录1.长草2.分考场1.长草 题目 链接#xff1a; 长草 - 蓝桥云课 (lanqiao.cn) 题目描述 小明有一… 作者指针不指南吗 专栏蓝桥杯倒计时冲刺 马上就要蓝桥杯了最后的这几天尤为重要不可懈怠哦 文章目录1.长草2.分考场1.长草 题目 链接 长草 - 蓝桥云课 (lanqiao.cn) 题目描述 小明有一块空地他将这块空地划分为 n 行 m 列的小块每行和每列的长度都为 1。 小明选了其中的一些小块空地种上了草其他小块仍然保持是空地。 这些草长得很快每个月草都会向外长出一些如果一个小块种了草则它将向自己的上、下、左、右四小块空地扩展 这四小块空地都将变为有草的小块。请告诉小明k 个月后空地上哪些地方有草。 输入描述 输入的第一行包含两个整数 n*,*m。 接下来 n 行每行包含 m 个字母表示初始的空地状态字母之间没有空格。如果为小数点表示为空地如果字母为 g表示种了草。 接下来包含一个整数 k。 其中2≤n,m≤10001≤k≤1000。 输出描述 输出 n 行每行包含 m 个字母表示 k 个月后空地的状态。如果为小数点表示为空地如果字母为 g表示长了草。 输入输出样例 示例 输入 4 5
.g...
.....
..g..
.....
2输出 gggg.
gggg.
ggggg
.ggg.第一次 AC 0% #includebits/stdc.h
using namespace std;typedef pairint,int PII;
int const N1100;int n,m,k;
char g[N][N];
int d[N][N];
queuePII q;void bfs()
{int dx[4]{0,0,-1,1},dy[4]{1,-1,0,0};while(q.size()){auto tq.front();q.pop();for(int i0;i4;i){int xt.firstdx[i],yt.seconddy[i];if(d[x][y]-1xnx1ymy1g[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 i1;in;i)for(int j1;jm;j){cing[i][j];if(g[i][j]g){q.push({i,j});d[i][j]0;}}scanf(%d,k);bfs();for(int i1;in;i){for(int j1;jm;j){coutg[i][j];}coutendl;}return 0;
}题解 #includebits/stdc.h
using namespace std;typedef pairint,int PII;
int const N1100;int n,m,k,cnt;
char g[N][N];
int d[N][N];
queuePII q;
int len;void bfs()
{int dx[4]{0,0,-1,1},dy[4]{1,-1,0,0};while(q.size()k0){auto tq.front();q.pop();for(int i0;i4;i){int xt.firstdx[i],yt.seconddy[i];if(d[x][y]-1xnx1ymy1g[x][y].){q.push({x,y});g[x][y]g;}}len--; //一个点向四周扩展完之后len--表示这层的一个点已经完成扩展 //这里是重点if(len0) //len 0 说明这层的点已经全部完成扩展令 len 重新等于刚扩展过程中放进去点的个数即q.size(),我们之前的点都已经pop掉了所以现在队列里面的点都是新放进去属于下一层的点并且层数k--{k--;lenq.size();}}}int main()
{scanf(%d%d,n,m);memset(d,-1,sizeof d);for(int i1;in;i)for(int j1;jm;j){cing[i][j];if(g[i][j]g){q.push({i,j});}}lenq.size(); //最开始计往里面放了几个元素 lenq.size( )scanf(%d,k);bfs();for(int i1;in;i){for(int j1;jm;j){coutg[i][j];}coutendl;}return 0;
}反思 第一次的扩展层数不正确代码没有实现成功 题解中的记录扩展层数的方式 最开始计往里面放了几个元素 lenq.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% #includebits/stdc.h
using namespace std;const int N110;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];ansmax(ans,s[b]);p[b]find(p[a]);
}int main()
{scanf(%d%d,n,m);for(int i1;in;i){p[i]i;s[i]1;}while(m--){int a,b;scanf(%d%d,a,b);add(a,b);}coutans;return 0;} 想错了这题长得真像并查集a和b认识b和c认识但是a和b不一定认识 经过思考我的思路 先把n个数放在一个房间里面a,b 认识把其中一个从他们房间里面移出去 移到隔壁房间隔壁房间有认识的人往下轮直到找到没有认识的人房间如果都不行就新建一个房间 ans 怎么实现呢 题解 #includebits/stdc.h
using namespace std;const int N110;int n,m;
bool g[N][N]; //矩阵数组两个人认识为1不认识为 0
vectorintq[N]; //定义一个二维空间数组
int ans0x3f3f3f3f; //定义最后需要的房间bool check(int id,int p) //判断 p 这个考场能不能放 id 这个人
{for(int j0;jq[p].size();j) //q[p].size() 表示考场的人数精髓{if(g[id][q[p][j]])return false;}return true;
} void dfs(int id,int cnt)
{if(cntans) //剪枝一定不是最小的结果回溯return;if(idn1) // 所有人 都遍历了回溯{ansmin(ans,cnt); return;}for(int p1;pcnt;p) //遍历每一个考场 {if(check(id,p)) //考场里没有熟人 {q[p].push_back(id); //id放在 p这个考场里面dfs(id1,cnt); //放下一个 学生q[p].pop_back(); //恢复现场} }if(cntn) //经过上面的遍历每一个考场没有 dfs 说明没有考场可以放 idso开一个新的考场{q[cnt1].push_back(id); //cnt1dfs(id1,cnt1); q[cnt1].pop_back(); //回复现场}}int main()
{cinnm;while(m--){int a,b;cinab;if(a!b)g[a][b]1,g[b][a]1;}dfs(1,0); //编号为 1房间数号 0 coutans; return 0;
}反思 怎么实现呢我想了用邻接表但是没有实现出来 题解中的vector二维数组真是妙 vector 二维数组 vectorint q[m] 表示可以往 q[1]q[2] 里面放一个数组 q[2][3] 表示 q[2]这个数组的 第 3个元素根据上面题中理解更透彻 而且还可以 使用 q[2].size() 就很方便 审题避免整个思路方向性出现错误dfs 会使用成 并查集 老生常谈
