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

Designer 小郑

发布于 2023-07-31 15:23:41

1290

发布于 2023-07-31 15:23:41

文章被收录于专栏：跟着小郑学JAVA跟着小郑学JAVA

本文是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!

#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

#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

#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

#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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-07-15，如有侵权请联系 cloudcommunity@tencent.com 删除

acm