本文是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!
1. #include<iostream> 2. #include<algorithm> 3. #include<queue> 4. #include<stack> 5. using namespace std; 6. 7. char aa[5]; 8. int main() 9. { 10. int t, i, j; 11. cin >> t; 12. while (t--){ 13. char bb[3]; 14. int m, k; 15. cin >> m >> aa; 16. if (aa[2] == 'F'){ 17. queue<int>q1; 18. while (!q1.empty()){ 19. q1.pop(); 20. } 21. while (m--){ 22. cin >> bb; 23. if (bb[0] == 'O' && q1.empty() == 1) 24. cout << "None" << endl; 25. else if (bb[0] == 'O'){ 26. cout << q1.front() << endl; 27. q1.pop(); 28. } 29. else{ 30. cin >> k; 31. q1.push(k); 32. } 33. } 34. } 35. else{ 36. stack<int>s1; 37. while (!s1.empty()){ 38. s1.pop(); 39. } 40. while (m--) { 41. cin >> bb; 42. if (bb[0] == 'O' && s1.empty() == 1) { 43. cout << "None" << endl; 44. } 45. else if (bb[0] == 'O'){ 46. cout << s1.top() << endl; 47. s1.pop(); 48. } 49. else{ 50. cin >> k; 51. s1.push(k); 52. } 53. } 54. } 55. } 56. return 0; 57. }
B题： Oil Deposits
1. #include<iostream> 2. #include<algorithm> 3. using namespace std; 4. 5. int n, m; 6. char a[102][102]; 7. int ii[8] = { 0,0,1,-1,1,-1,1,-1 };//八个方向 8. int jj[8] = { 1,-1,0,0,1,-1,-1,1 };//八个方向 9. void dfs(int i, int j){ 10. if (i < 0 || i >= n || j < 0 || j >= m) return; 11. int q; 12. a[i][j] = '*'; 13. for (q = 0; q < 8; q++){ 14. if (a[i + ii[q]][j + jj[q]] == '@'){ 15. dfs(i + ii[q], j + jj[q]); 16. } 17. } 18. } 19. int main(){ 20. int i, j, sum; 21. while (~scanf("%d%d%*c", &n, &m)){ 22. if (n == 0 && m == 0) break; 23. memset(a, 0, sizeof(a)); 24. sum = 0; 25. for (i = 0; i < n; i++){ 26. scanf("%s", a[i]); 27. } 28. for (i = 0; i < n; i++){ 29. for (j = 0; j < m; j++){ 30. if (a[i][j] == '@'){ 31. sum++; 32. dfs(i, j); 33. } 34. } 35. } 36. cout << sum << endl; 37. } 38. return 0; 39. }
C题：Rescue
1. #include<iostream> 2. #include<algorithm> 3. #include<queue> 4. using namespace std; 5. 6. int n, m; 7. char a[202][202]; 8. bool v[202][202]; 9. int ii[8] = { 0,0,1,-1 }; 10. int jj[8] = { 1,-1,0,0 }; 11. 12. struct ren{ 13. int x; 14. int y; 15. int bushu; 16. friend bool operator < (const ren& a, const ren& b){ 17. return a.bushu > b.bushu; 18. } 19. }tianshi; 20. 21. int bfs(ren tianshi) 22. { 23. memset(v, false, sizeof(v)); 24. priority_queue <ren>q1; 25. q1.push(tianshi); 26. while (!q1.empty()){ 27. ren li, ll; 28. li = q1.top(); 29. v[li.x][li.y] = true; 30. q1.pop(); 31. int i; 32. for (i = 0; i < 4; i++){ 33. if (a[li.x + ii[i]][li.y + jj[i]] == '.' && v[li.x + ii[i]][li.y + jj[i]] == false){ 34. ll.bushu = li.bushu + 1; 35. ll.x = li.x + ii[i]; 36. ll.y = li.y + jj[i]; 37. q1.push(ll); 38. } 39. else if (a[li.x + ii[i]][li.y + jj[i]] == 'x' && v[li.x + ii[i]][li.y + jj[i]] == false){ 40. ll.bushu = li.bushu + 2; 41. ll.x = li.x + ii[i]; 42. ll.y = li.y + jj[i]; 43. q1.push(ll); 44. } 45. else if (a[li.x + ii[i]][li.y + jj[i]] == '#') continue; 46. else if (a[li.x + ii[i]][li.y + jj[i]] == 'r') return li.bushu + 1; 47. } 48. } 49. return -1; 50. } 51. int main() 52. { 53. int i, j; 54. while (~scanf("%d%d%*c", &n, &m)){ 55. if (n == 0 && m == 0) break; 56. memset(a, 0, sizeof(a)); 57. for (i = 0; i < n; i++){ 58. scanf("%s", a[i]); 59. } 60. for (i = 0; i < n; i++){ 61. bool fff = false; 62. for (j = 0; j < m; j++){ 63. if (a[i][j] == 'a'){ 64. tianshi.x = i; 65. tianshi.y = j; 66. tianshi.bushu = 0; 67. fff = true; 68. break; 69. } 70. } 71. if (fff) break; 72. } 73. int tt = bfs(tianshi); 74. if (tt == -1) 75. cout << "Poor ANGEL has to stay in the prison all his life." << endl; 76. else 77. cout << tt << endl; 78. } 79. return 0; 80. }
1. #include<iostream> 2. #include<algorithm> 3. #include<queue> 4. using namespace std; 5. 6. int n, m, sj; 7. char a[10][10]; 8. bool v[10][10]; 9. bool you = false; 10. int ii[4] = { 0,0,1,-1 }; 11. int jj[4] = { 1,-1,0,0 }; 12. void dfs(int x, int y, int shijian){ 13. if (a[x][y] == 'D' && shijian == sj){ 14. you = true; 15. return; 16. } 17. else if (shijian >= sj || you == true) 18. return; 19. else if (a[x][y] == '.' || a[x][y] == 'S'){ 20. v[x][y] = true; 21. if (x < n - 1 && v[x + 1][y] == false){ 22. dfs(x + 1, y, shijian + 1); 23. } 24. if (x > 0 && v[x - 1][y] == false){ 25. dfs(x - 1, y, shijian + 1); 26. } 27. if (y < m - 1 && v[x][y + 1] == false){ 28. dfs(x, y + 1, shijian + 1); 29. } 30. if (y > 0 && v[x][y - 1] == false){ 31. dfs(x, y - 1, shijian + 1); 32. } 33. v[x][y] = false; 34. } 35. } 36. int main(){ 37. int i, j; 38. while (~scanf("%d%d%d%*c", &n, &m, &sj)){ 39. you = false; 40. if (n == 0 && m == 0 && sj == 0) break; 41. memset(a, 0, sizeof(a)); 42. for (i = 0; i < n; i++){ 43. scanf("%s", a[i]); 44. } 45. int ss, ee; 46. for (i = 0; i < n; i++){ 47. for (j = 0; j < m; j++){ 48. if (a[i][j] == 'S'){ 49. ss = i; ee = j; 50. } 51. } 52. } 53. dfs(ss, ee, 0); 54. if (you) cout << "YES" << endl; 55. else cout << "NO" << endl; 56. } 57. return 0; 58. }
1. #include<iostream> 2. #include<algorithm> 3. using namespace std; 4. 5. int n, m; 6. char a[102][102]; 7. bool v[102][102]; 8. int ii[4] = { 0,0,1,-1 };//四个方向 9. int jj[4] = { 1,-1,0,0 };//四个方向 10. bool run(int x, int y){ 11. if (x >= 0 && x < n && y >= 0 && y < m) return true; 12. return false; 13. } 14. void dfs(int x, int y){ 15. if (a[x][y] == '.') return; 16. a[x][y] = '.'; 17. int i; 18. for (i = 0; i < 4; i++){ 19. int xx = x + ii[i]; 20. int yy = y + jj[i]; 21. if (run(xx, yy)){ 22. dfs(xx, yy); 23. } 24. } 25. } 26. int main(){ 27. int i, j, t, sum; 28. cin >> t; 29. while (t--){ 30. sum = 0; 31. scanf("%d%d%*c", &n, &m); 32. for (i = 0; i < n; i++){ 33. scanf("%s", a[i]); 34. } 35. memset(v, false, sizeof(v)); 36. for (i = 0; i < n; i++){ 37. for (j = 0; j < m; j++){ 38. if (a[i][j] == '#'){ 39. sum++; 40. dfs(i, j); 41. } 42. } 43. } 44. cout << sum << endl; 45. } 46. return 0; 47. }
