本文是2018年（大一升大二）的暑假集训中，“搜索”专题的课后练习，我事先拉了题目，然后把题解放这里，给听课的人一个参考代码。
比赛链接：https://vjudge.net/contest/238396 密码 ypacm
A题 HDU1702，B题 HDU1241，C题 HDU1242，D题 HDU1010，E题 HDU2952
简单介绍：
A题为最基础的栈、队列的应用 其中队列是先进先出，栈是先进后出。比如队列1进2进 出 出 只要输出1 2.
B题为求连通块的个数，可以深搜也可以广搜，看个人喜好，此题连通块为左右和斜对角线。
C题的意思是天使救小朋友，地图中a代表天使，r代表小朋友，x代表警察，点代表可以走的路，#代表是墙，杀死一个警察要一个单位时间，走一个格子也要1个单位时间，求天使最短多少时间可以解救小朋友，此题用广搜做会方便点。
D题的意思是一个人能不能从S走到D，如果可以走，输出yes，不能就输出no，x代表墙，点代表路，用广搜。
E题同B题一样求连通块的个数，只是这题只能是左右，不包含斜对角线，解法同B题。
下面给出我自己写的AC代码，纯手打原创，可能有很多可以改进的地方，欢迎大佬指出。
A题：ACboy needs your help again!
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
char aa[5];
int main()
{
int t, i, j;
cin >> t;
while (t--){
char bb[3];
int m, k;
cin >> m >> aa;
if (aa[2] == 'F'){
queue<int>q1;
while (!q1.empty()){
q1.pop();
}
while (m--){
cin >> bb;
if (bb[0] == 'O' && q1.empty() == 1)
cout << "None" << endl;
else if (bb[0] == 'O'){
cout << q1.front() << endl;
q1.pop();
}
else{
cin >> k;
q1.push(k);
}
}
}
else{
stack<int>s1;
while (!s1.empty()){
s1.pop();
}
while (m--) {
cin >> bb;
if (bb[0] == 'O' && s1.empty() == 1) {
cout << "None" << endl;
}
else if (bb[0] == 'O'){
cout << s1.top() << endl;
s1.pop();
}
else{
cin >> k;
s1.push(k);
}
}
}
}
return 0;
}B题： Oil Deposits
代码语言：javascript复制#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
char a[102][102];
int ii[8] = { 0,0,1,-1,1,-1,1,-1 };//八个方向
int jj[8] = { 1,-1,0,0,1,-1,-1,1 };//八个方向
void dfs(int i, int j){
if (i < 0 || i >= n || j < 0 || j >= m) return;
int q;
a[i][j] = '*';
for (q = 0; q < 8; q ){
if (a[i ii[q]][j jj[q]] == '@'){
dfs(i ii[q], j jj[q]);
}
}
}
int main(){
int i, j, sum;
while (~scanf("%d%d%*c", &n, &m)){
if (n == 0 && m == 0) break;
memset(a, 0, sizeof(a));
sum = 0;
for (i = 0; i < n; i ){
scanf("%s", a[i]);
}
for (i = 0; i < n; i ){
for (j = 0; j < m; j ){
if (a[i][j] == '@'){
sum ;
dfs(i, j);
}
}
}
cout << sum << endl;
}
return 0;
}C题：Rescue
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n, m;
char a[202][202];
bool v[202][202];
int ii[8] = { 0,0,1,-1 };
int jj[8] = { 1,-1,0,0 };
struct ren{
int x;
int y;
int bushu;
friend bool operator < (const ren& a, const ren& b){
return a.bushu > b.bushu;
}
}tianshi;
int bfs(ren tianshi)
{
memset(v, false, sizeof(v));
priority_queue <ren>q1;
q1.push(tianshi);
while (!q1.empty()){
ren li, ll;
li = q1.top();
v[li.x][li.y] = true;
q1.pop();
int i;
for (i = 0; i < 4; i ){
if (a[li.x ii[i]][li.y jj[i]] == '.' && v[li.x ii[i]][li.y jj[i]] == false){
ll.bushu = li.bushu 1;
ll.x = li.x ii[i];
ll.y = li.y jj[i];
q1.push(ll);
}
else if (a[li.x ii[i]][li.y jj[i]] == 'x' && v[li.x ii[i]][li.y jj[i]] == false){
ll.bushu = li.bushu 2;
ll.x = li.x ii[i];
ll.y = li.y jj[i];
q1.push(ll);
}
else if (a[li.x ii[i]][li.y jj[i]] == '#') continue;
else if (a[li.x ii[i]][li.y jj[i]] == 'r') return li.bushu 1;
}
}
return -1;
}
int main()
{
int i, j;
while (~scanf("%d%d%*c", &n, &m)){
if (n == 0 && m == 0) break;
memset(a, 0, sizeof(a));
for (i = 0; i < n; i ){
scanf("%s", a[i]);
}
for (i = 0; i < n; i ){
bool fff = false;
for (j = 0; j < m; j ){
if (a[i][j] == 'a'){
tianshi.x = i;
tianshi.y = j;
tianshi.bushu = 0;
fff = true;
break;
}
}
if (fff) break;
}
int tt = bfs(tianshi);
if (tt == -1)
cout << "Poor ANGEL has to stay in the prison all his life." << endl;
else
cout << tt << endl;
}
return 0;
}D题：Tempter of the Bone
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, sj;
char a[10][10];
bool v[10][10];
bool you = false;
int ii[4] = { 0,0,1,-1 };
int jj[4] = { 1,-1,0,0 };
void dfs(int x, int y, int shijian){
if (a[x][y] == 'D' && shijian == sj){
you = true;
return;
}
else if (shijian >= sj || you == true)
return;
else if (a[x][y] == '.' || a[x][y] == 'S'){
v[x][y] = true;
if (x < n - 1 && v[x 1][y] == false){
dfs(x 1, y, shijian 1);
}
if (x > 0 && v[x - 1][y] == false){
dfs(x - 1, y, shijian 1);
}
if (y < m - 1 && v[x][y 1] == false){
dfs(x, y 1, shijian 1);
}
if (y > 0 && v[x][y - 1] == false){
dfs(x, y - 1, shijian 1);
}
v[x][y] = false;
}
}
int main(){
int i, j;
while (~scanf("%d%d%d%*c", &n, &m, &sj)){
you = false;
if (n == 0 && m == 0 && sj == 0) break;
memset(a, 0, sizeof(a));
for (i = 0; i < n; i ){
scanf("%s", a[i]);
}
int ss, ee;
for (i = 0; i < n; i ){
for (j = 0; j < m; j ){
if (a[i][j] == 'S'){
ss = i; ee = j;
}
}
}
dfs(ss, ee, 0);
if (you) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}E题：Counting Sheep
代码语言：javascript复制#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
char a[102][102];
bool v[102][102];
int ii[4] = { 0,0,1,-1 };//四个方向
int jj[4] = { 1,-1,0,0 };//四个方向
bool run(int x, int y){
if (x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
void dfs(int x, int y){
if (a[x][y] == '.') return;
a[x][y] = '.';
int i;
for (i = 0; i < 4; i ){
int xx = x ii[i];
int yy = y jj[i];
if (run(xx, yy)){
dfs(xx, yy);
}
}
}
int main(){
int i, j, t, sum;
cin >> t;
while (t--){
sum = 0;
scanf("%d%d%*c", &n, &m);
for (i = 0; i < n; i ){
scanf("%s", a[i]);
}
memset(v, false, sizeof(v));
for (i = 0; i < n; i ){
for (j = 0; j < m; j ){
if (a[i][j] == '#'){
sum ;
dfs(i, j);
}
}
}
cout << sum << endl;
}
return 0;
}
