牛客春招刷题训练营 - 2025.3.13 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 提取不重复的整数

简要题意

给一个整数，反向输出这个数，但跳过重复的数位。

Solution

字符串读入，反过来输出，输出时判一下有没有见过就好。

Code

void R()
{
	map<char,bool> vis;
	string s;
	cin>>s;
	for (int i=s.size()-1;i>=0;i--)
		if (!vis.count(s[i]))
		{
			vis[s[i]]=1;
			cout<<s[i];
		}
	return;
}

Medium 句子逆序

简要题意

给定一行若干个单词，将这些单词按相反顺序输出。

Solution

和 2025/3/10 的 Easy 同理，我们用 while (cin>>s) 读入。

然后插到一个 vector 里，reverse() 后输出就好。

Code

void R()
{
	string s;
	vector<string> t;
	while (cin>>s)
		t.push_back(s);
	reverse(t.begin(),t.end());
	for (auto &s:t)
		cout<<s<<' ';
	return;
}

Hard 迷宫问题

简要题意

给定一个 的四联通网格图，网格要么是通路要么是墙，找一条 到 的不撞墙的路径。

Solution

又是小模拟。

题目保证有解，我们直接 DFS 出一条路径，回溯时依次输出当前点就好。

注意到要求从起点输出到终点，正着搜需要把途径点先存下，倒着搜就不用了。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int>> a(n,vector<int>(m)),vis(a);
	vector<array<int,2>> ans;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			cin>>a[i][j];

	auto dfs=[&](auto &self,int x,int y)->bool
	{
		if (vis[x][y]||a[x][y]) return 0;
		else vis[x][y]=1;
		if (!x&&!y) goto ed;
		if (x&&self(self,x-1,y))
			goto ed;
		if (y&&self(self,x,y-1))
			goto ed;
		if (x+1<n&&self(self,x+1,y))
			goto ed;
		if (y+1<m&&self(self,x,y+1))
			goto ed;
		return 0;

		ed:ans.push_back({x,y});
		return 1;
	};

	dfs(dfs,n-1,m-1);
	for (auto [x,y]:ans)
		cout<<'('<<x<<','<<y<<")\n";
	return;
}