---

小丑的身份证和复印件 （BFS + Floyd）

原创 于 2024-05-09 19:02:05 发布 · 粉丝可见 · 940 阅读 · 3 · 8 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/138614864

本题链接： 登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

cobol<br/>2 10<br/>(JOKERjoke<br/>#####asdr)<br/>

12

思路：

根据题意，要求最短时间，实际上也可以理解为最短距离。

所以应该联想到有关最短距离的算法，在这里给出的 n，m是100，所以我们可以暴力求最短距离即可，身份碎片虽然分大小写，但是它们都是唯一的点，所以可以通过Floyd，记录每个点之间的最短距离，随后累加即可，其次这里的最短距离可以用BFS求得最短距离。注意一个细节，初始化无穷大的时候，尽量小一些，否则多个INF累加爆 long long 就会答案错误。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#define endl '\n'
#define int long long
#define x first
#define y second
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();

signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
	// cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
using PII = pair<int,int>;
int n,m;
PII rem[256];	// rem 记录最短路中字符的位置
char g[110][110];

int dist[256][256];	// Floyd最短距离

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
// BFS 求字符a 到字符 b 之间的最短路
inline int Dist(char a,char b)
{
	// 标记是否走动过当前位置
	vector<vector<bool>>st(110,vector<bool>(110,false));
	// 判断是否可以走动的条件
	auto isRun = [&](int x,int y)->bool
	{
		return (x >= 0 and x < n and y >= 0 and y < m and !st[x][y] and g[x][y] != '#');
	};
	
	// BFS 求最短路
	int step = 0;
	queue<PII>q;
	q.emplace(rem[a]);
	while(q.size())
	{
		int sz = q.size();
		while(sz--)
		{
			PII now = q.front();
			q.pop();
			if(g[now.x][now.y] == b)
			{
				rem[b] = now;	// 记录当前最短路的位置
				return step;
			}
			st[now.x][now.y] = true;
			for(int i = 0;i < 4;++i)
			{
				int bx = now.x + dx[i];
				int by = now.y + dy[i];
				if(isRun(bx,by))
				{
					st[bx][by] = true;
					q.emplace(PII(bx,by));
				}
			}
		}
		++step;
	}
	// 返回无穷大
	return INT_MAX;
}

inline void solve()
{
	// 拿取碎片的方案
	vector<char>plan = {'J','O','K','E','R','j','o','k','e','r'};

	cin >> n >> m;
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
		{
			char c;
			cin >> c;
			g[i][j] = c;
			// 存储好起点和终点的位置
			if(c == '(') rem[c] = PII(i,j);
			if(c == ')') rem[c] = PII(i,j);
		}
	}
	
	// 存储起点到各个字符之间的最短距离
	for(char &p:plan) dist['('][p] = Dist('(',p);
	
	// 存储终点到各个字符之间的最短距离
	for(char &p:plan) dist[p][')'] = Dist(')',p);
	
	// 存储各个点之间的最短距离
	for(char &st:plan)
	{
		for(char &ed:plan)
		{
			if(st == ed) continue;
			dist[st][ed] = Dist(st,ed);
		}
	}
	
	sort(All(plan));
	// 全排列遍历所有的捡碎片方案
	// 获取最小的一种答案即可
	int ans = INT_MAX;
	do
	{
		int res = 0;
		res += dist['('][*plan.begin()]; //累加起点开始的最短距离
		for(int i = 1;i < 10;++i) res += dist[plan[i - 1]][plan[i]];	// 按顺序累加最短距离
		res += dist[plan.back()][')'];	// 累加最后到终点最短距离
		ans = min(ans,res);

	}while(next_permutation(All(plan)));

	if(ans >= INT_MAX) cout << "-1" << endl;
	else cout << ans << endl;
}

最后提交：