编程笔记|蓝桥杯模拟赛收获（8题）
本文非原创，仅为个人的学习笔记
下面附上参考网址：
C++ cin.get用法（详解版）
C++ : cin.get（）函数和cin函数的使用
c++中队列函数queue的常用
第八题
【问题描述】
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
请告诉小明，k 个月后空地上哪些地方有草。
代码：
#include <iostream>
#include <queue>
//伪代码原来是加在using namespace 上面。
#define loop(i, x, y) for(register int i = x;i <= y;i++)
using namespace std;
//草地上的一块
struct block {
int i;
int j;
int month;
};//i、j记录行列数，month记录第几个月长的。
//这个是加到队列里的一个元素。
//这个是构造一个上下左右的坐标，不需要写那么多代码
//用const相比不用节省变量储存空间
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
//全局变量?
int vis[1000][1000]{};
int N, M, K;
int main() {
//。。竞赛专用读写加速代码。。
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
//这个是用来计时的参数^_^？
int a = clock();
cin >> N >> M;
//建立队列的语句？
queue<block> q;
//读换行符
char next_char;
cin.get(next_char);//cin.get与cin>>的区别？
while (next_char != '\n')cin.get(next_char);
loop(i, 0, N - 1) {
loop(j, 0, M - 1) {
cin.get(next_char);
if (next_char == 'g') {
q.push({i, j, 0});
vis[i][j] = 1;
}
}
cin.get(next_char);
while (next_char != '\n')cin.get(next_char);
}
cin >> K;
while (!q.empty()) {
block b = q.front();
q.pop();
int month = b.month;
if (month < K) {
loop(i, 0, 3) {
int nx = b.i + dx[i];
int ny = b.j + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < M && vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q.push({nx, ny, month + 1});
}
}
}
}
loop(i, 0, N - 1) {
loop(j, 0, M - 1) {
if (vis[i][j] == 1) cout << 'g';
else cout << '.';
}
cout << endl;
}
clog << clock() - a << endl;
return 0;
}
知识点:
1.队列
包含在头文件<queue>中
队列的定义：
queue<block> q;
<>中是类型名，这里的block是自定义结构体。
关于queue的函数：
- push()
队列中由于是先进先出，push即在队尾插入一个元素，如：
queue<string> q;
q.push("Hello World!");
//----------//
struct block {
int i;
int j;
int month;
};
queue<block> q;
q.push({i, j, 0});
- pop()
将队列中最靠前位置的元素弹出，是没有返回值的void函数。如：
q.pop();//此题中将队列中的元素长完草就把他拿掉。
- size()
返回队列中元素的个数，返回值类型为unsigned int。如：
queue<string> q;
cout<<q.size()<<endl;
q.push("Hello World!");
q.push("China");
cout<<q.size()<<endl;
输出分别为0 和 2.
- empty()
判断队列是否为空的，如果为空则返回true。
此题中使用dfs，语句while(!q.empty()){}是如果不为空就继续进行长草。 - front()
返回值为队列中的第一个元素，也就是最早、最先进入队列的元素。
此题中block b=q.front();是将头元素先拿出来长草，hhh。 - back()
返回队列中最后一个元素，也就是最晚进去的元素。
2.三行加速代码
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
3.cin系列
- cin
1.cin的最常用的用法是输入一个数字
#include <iostream>
using namespace std;
main ()
{
int a,b;
cin>>a>>b
cout<<a+b<<endl;
}
注意:>> 是会过滤掉不可见字符（如 空格 回车，TAB 等）
你在上面输入32(空格)2(回车)和输入32(回车)2(回车)的结果都是34
cin>>noskipws>>input[j];//不想略过空白字符，那就使用 noskipws 流控制
2.接受一个字符串，遇“空格”、“TAB”、“回车”都结束。
#include <iostream>
using namespace std;
main ()
{
char a[20];
cin>>a;
cout<<a<<endl;
}
输入：jkljkljkl
输出：jkljkljkl
输入：jkljkl jkljkl //遇空格结束
输出：jkljkl
- cin.get()
读入一个字符，相当于C中的getchar()
#include <iostream>
using namespace std;
main ()
{
char ch;
ch=cin.get(); //或者cin.get(ch);
cout<<ch<<endl;
}
4.clock()
clock()函数存在于头文件<ctime>里，
clock()是返回int类型数值的系统时间，
利用开始与结束时的时间差可以计算程序运行时间（单位：ms）。
分析：
首先为什么要多几行代码读入换行符：
结合cin的用法，这里用cin>>达不到我们想要的效果。
例如，因为它会忽略掉所有前导白色空格，所以使用 cin>> 就不可能仅输入一个空格或回车符。除非用户输入了空格键、制表符之外的其他字符，否则程序将不可能通过 cin 语句继续执行（一旦输入了这样的字符，在程序可以继续下一个语句之前，仍然需要按回车键）。因此，要求用户“按回车键继续”的程序，不能使用 >> 运算符只读取按回车键的行为。
拿这个题举例子。
加入要求的输入格式是在输入MN后还要额外加个回车，那么这一行代码（如图),就有他的用，但我尝试注释了最后一行while，结果还是没变，所以我觉得之前吃掉换行符没必要。
我发现这道题里这两句都注释掉结果还是一样。不过还是学到了。
此处的技巧还有
#define loop(i, x, y) for(register int i = x;i <= y;i++)
//....//
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
然后在之后的代码里调用dx[i]、dy[i],tql我即便现在每句话都看得懂，也要能写出来才好。我急需即学即用的能力。看别人的代码，一个个理解真的不耗什么脑力，要自己想出来才最厉害，这需要许多逻辑思维，比如这里的while（）和if（）括弧里的东西要想出来还是要花点心的。
while (!q.empty()) {
block b = q.front();
q.pop();
int month = b.month;
if (month < K) {
loop(i, 0, 3) {
int nx = b.i + dx[i];
int ny = b.j + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < M && vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q.push({nx, ny, month + 1});
}
}
}
}
另外dfs的算法也值得学习，直接将每个点标记，还标记月份，当第一次将矩阵读入队列，就和矩阵无关了之后的长草都无需访问矩阵这么大的一个储存空间。
