ACM刷题之路（四）2018暑假实验室集训——深广搜专题题解

浅浅的花香味﹌ 2024-02-18 21:38 19阅读 0赞

本文是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!**][ACboy needs your help again]

#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**][_Oil Deposits]

#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**][Rescue]

#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**][Tempter of the Bone]

#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**][Counting Sheep]

#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;
    }

[ACboy needs your help again]: https://vjudge.net/problem/HDU-1702
[_Oil Deposits]: https://vjudge.net/problem/HDU-1241
[Rescue]: https://vjudge.net/problem/HDU-1242
[Tempter of the Bone]: https://vjudge.net/problem/HDU-1010
[Counting Sheep]: https://vjudge.net/problem/HDU-2952