2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）提供，

OJ：可以到http://oj.ecustacm.cn/交題，從第3頁開始是歷年真題：http://oj.ecustacm.cn/problemset.php?page=3

一、2017年藍橋杯軟體類 C語言大學A組

共10題，題目總覽：
1、迷宮
2、跳蚱蜢
3、魔方狀態
4、方格分割
5、字母組串
6、最大公共子串
7、正則問題
8、包子湊數
9、分巧克力
10、油漆面積

第一天：2021.1.3日

1. 迷宮

題目鏈接： http://oj.ecustacm.cn/problem.php?id=1317

（1）投機取巧的搞法
??根據本文的“附考生須知”，第1題是填空題，只交答案就行了，如果不想編碼，直接用手一個個去數那100個點，幾分鐘就數完了，答案是31，比編碼還要快，
??在OJ上這樣交就能AC：

#include<iostream>
using namespace std;
int main(){
   cout << 31 << endl;
   return 0;
}

（2）還是用這題來練練DFS編碼吧
題解：
??一道搜索題，可以選擇暴力dfs，代碼簡短
??我寫的稍微長一點，但可以確保每個點只走到一次，稍微優化了那么一丟丟
??此題唯一的坑點是提交到OJ時，千萬不要寫輸入！！555
??直接輸出一個數字就好惹…
參考代碼：（羅老師注：倪文迪沒有用遞回寫DFS，參考這篇用遞回寫的DFS，更好懂：https://www.cnblogs.com/-citywall123/p/12316760.html）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;

int mp[20][20];
int vis[20][20];
bool tag[200];
int cnt[200];

int X[] = {0, 0, 0, -1, 1};
int Y[] = {0, -1, 1, 0, 0};

void solve(int x, int y, int id)
{
	while(x >= 1 && x <= 10 && y >= 1 && y <= 10 && !vis[x][y]){
		vis[x][y] = id;
		cnt[id]++;
		int now = mp[x][y];
		x += X[now];
		y += Y[now];
	}
	if(x < 1 || x > 10 || y < 1 || y > 10){
		tag[id] = true;
		return ;
	}
	if(vis[x][y]){
		if(tag[vis[x][y]])	tag[id] = true;	
	}
	return ;
}

int main(){
	for(int i = 1 ; i <= 10 ; i++){
		string s; cin >> s;
		for(int j = 0 ; j < 10 ; j++){
			if(s[j] == 'L')	mp[i][j + 1] = 1;
			else if(s[j] == 'R') mp[i][j + 1] = 2;
			else if(s[j] == 'U') mp[i][j + 1] = 3;
			else if(s[j] == 'D') mp[i][j + 1] = 4;
		}
	}
	
	int	id = 1;
	for(int i = 1 ; i <= 10 ; i++){
		for(int j = 1 ; j <= 10 ; j++){
			if(!vis[i][j]){
				solve(i, j, id);
				id++;
			}
		}
	}
	/*for(int i = 1 ; i <= 10 ; i++){
		for(int j = 1 ; j <= 10 ; j++){
			printf("%3.d",vis[i][j]);
		}
		cout << endl;
	}*/
	
	int res = 0;
	for(int i = 1 ; i < id ; i++){
		if(tag[i])	res += cnt[i];
	}
	printf("%d\n", res);
	
	return 0;
}

附：2017年第八屆藍橋杯大賽個人賽省賽（軟體類） C/C++ 大學A組考生須知

考生須知：
???考試開始后，選手首先下載題目，并使用考場現場公布的解壓密碼解壓試題，
???考試時間為4小時，時間截止后，提交答案無效，
???在考試強制結束前，選手可以主動結束考試（需要身份驗證），結束考試后將無法繼續提交或瀏覽答案，
???選手可瀏覽自己已經提交的答案，被瀏覽的答案允許拷貝，
???對同一題目，選手可多次提交答案，以最后一次提交的答案為準，
???選手切勿在提交的代碼中書寫“姓名”、“考號”，“院校名”等與身份有關的資訊或其它與競賽題目無關的內容，否則成績無效，
???選手必須通過瀏覽器方式提交自己的答案，選手在其它位置的作答或其它方式提交的答案無效，
???試題包含三種型別：“結果填空”、“代碼填空”與“程式設計”，
??結果填空題：要求選手根據題目描述直接填寫結果，求解方式不限，不要求源代碼，
??把結果填空的答案直接通過網頁提交即可，不要書寫多余的內容，
??代碼填空題：要求選手在弄清給定代碼作業原理的基礎上填寫缺失的部分，使得程式邏輯正確、完整，
??把代碼填空的答案（僅填空處的答案，不包括題面已存在的代碼或符號）直接通過網頁提交即可，不要書寫多余的內容，
??使用ANSI C/ANSI C++ 標準，不要依賴作業系統或編譯器提供的特殊函式，
??程式設計題目：要求選手設計的程式對于給定的輸入能給出正確的輸出結果，考生的程式只有能運行出正確結果才有機會得分，
??注意：在評卷時使用的輸入資料與試卷中給出的示例資料可能是不同的，選手的程式必須是通用的，不能只對試卷中給定的資料有效，
??對于編程題目，要求選手給出的解答完全符合ANSI C++標準，不能使用諸如繪圖、Win32API、中斷呼叫、硬體操作或與作業系統相關的API，
??代碼中允許使用STL類別庫，
??注意: main函式結束必須回傳0
??注意: 所有依賴的函式必須明確地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案，
??所有原始碼必須在同一檔案中，除錯通過后，拷貝提交，
??提交時，注意選擇所期望的編譯器型別，

1.結果填空 (滿分5分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，

2.結果填空 (滿分11分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，

3.結果填空 (滿分13分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，

4.結果填空 (滿分17分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，只要求提交結果，
??必須通過瀏覽器提交答案，

5.代碼填空 (滿分7分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，
??只要求填寫缺失的代碼部分，千萬不要畫蛇添足，填寫多余的已有代碼或符號，
??必須通過瀏覽器提交答案，

6.代碼填空 (滿分9分)
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，不限解決問題的方式，
??只要求填寫缺失的代碼部分，千萬不要畫蛇添足，填寫多余的已有代碼或符號，
??必須通過瀏覽器提交答案，

7.程式設計（滿分19分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意：在評卷時使用的輸入資料與試卷中給出的示例資料可能是不同的，選手的程式必須是通用的，不能只對試卷中給定的資料有效，
??仔細閱讀程式的輸入、輸出要求，千萬不要輸出沒有要求的、多余的內容，例如：“請您輸入xx資料：”，
??建議仔細閱讀示例，不要想當然！
??程式處理完一個用例的資料后，立即退出（return 0），千萬不要回圈等待下一個用例的輸入，
??程式必須使用標準輸入、標準輸出，以便于機器評卷時重定向，
??對于編程題目，要求選手給出的解答完全符合ANSI C++標準，不能使用諸如繪圖、Win32API、中斷呼叫、硬體操作或與作業系統相關的API，
??代碼中允許使用STL類別庫，
??注意: main函式結尾需要return 0
??注意: 所有依賴的函式必須明確地在源檔案中 #include ， 不能通過工程設定而省略常用頭檔案，
??所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，
??提交時，注意選擇所期望的編譯器型別，

8.程式設計（滿分21分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題

9.程式設計（滿分23分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題

10.程式設計（滿分25分）
??問題的描述在考生檔案夾下對應題號的“題目.txt”中，相關的參考檔案在同一目錄中，請先閱讀題目，必須通過編程的方式解決問題，
??注意事項同上題