編程筆記|藍橋杯模擬賽收獲（8題）
本文非原創(chuàng)串结，僅為個人的學習筆記
下面附上參考網址：
C++ cin.get用法（詳解版）
C++ : cin.get（）函數和cin函數的使用
c++中隊列函數queue的常用
第八題
【問題描述】
小明有一塊空地，他將這塊空地劃分為 n 行 m 列的小塊苇本，每行和每列的長度都為 1贡茅。
小明選了其中的一些小塊空地骂束，種上了草咪奖，其他小塊仍然保持是空地。
這些草長得很快治筒，每個月屉栓，草都會向外長出一些，如果一個小塊種了草耸袜，則它將向自己的上友多、下、左堤框、右四小塊空地擴展域滥，這四小塊空地都將變?yōu)橛胁莸男K。
請告訴小明蜈抓，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相比不用節(jié)省變量儲存空間
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>>的區(qū)別蟋软？
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()){}是如果不為空就繼續(xù)進行長草滩援。 - 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類型數值的系統(tǒng)時間技竟，
利用開始與結束時的時間差可以計算程序運行時間（單位：ms）。
分析：
首先為什么要多幾行代碼讀入換行符：
結合cin的用法屈藐，這里用cin>>達不到我們想要的效果榔组。
例如，因為它會忽略掉所有前導白色空格联逻，所以使用 cin>> 就不可能僅輸入一個空格或回車符搓扯。除非用戶輸入了空格鍵、制表符之外的其他字符包归，否則程序將不可能通過 cin 語句繼續(xù)執(zhí)行（一旦輸入了這樣的字符锨推，在程序可以繼續(xù)下一個語句之前，仍然需要按回車鍵）。因此换可，要求用戶“按回車鍵繼續(xù)”的程序椎椰，不能使用 >> 運算符只讀取按回車鍵的行為。
拿這個題舉例子沾鳄。
加入要求的輸入格式是在輸入MN后還要額外加個回車慨飘，那么這一行代碼（如圖),就有他的用，但我嘗試注釋了最后一行while译荞，結果還是沒變瓤的，所以我覺得之前吃掉換行符沒必要。
我發(fā)現這道題里這兩句都注釋掉結果還是一樣吞歼。不過還是學到了圈膏。
此處的技巧還有
#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的算法也值得學習忽刽，直接將每個點標記诱贿，還標記月份范删，當第一次將矩陣讀入隊列，就和矩陣無關了之后的長草都無需訪問矩陣這么大的一個儲存空間。
