网站建设教程免费,去哪里找做网站,机械类网站如何做网站优化,丽水手机网站建设本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网
题目#xff1a; 样例#xff1a; 输入 2 10
(JOKERjoke
#####asdr) 输出 12
思路#xff1a; 根据题意#xff0c;要求最短时间#xff0c;实际上也可以理解为最短距离。 所以应该联想到有关最短距离的算法登录—专业IT笔试面试备考平台_牛客网
题目 样例
输入 2 10
(JOKERjoke
#####asdr)
输出 12
思路 根据题意要求最短时间实际上也可以理解为最短距离。 所以应该联想到有关最短距离的算法在这里给出的 nm是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 pairint,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)
{// 标记是否走动过当前位置vectorvectorboolst(110,vectorbool(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;queuePIIq;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()
{// 拿取碎片的方案vectorcharplan {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;
}
最后提交
