牛客多校补题3
2022/7/31 23:33:51
本文主要是介绍牛客多校补题3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
title: 牛客多校补题3
author: Sun-Wind
date: July 26, 2022
J
思路
模拟+搜索,比赛的时候就一个细节写错了
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N = 5e5 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f; int h[5*N], e[20 * N], ne[20 * N], idx; int dist[5*N]; int a[N][5]; int n; int s1, s2, t1, t2; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } struct node { int x, y, z; }; void bfs() { map<pair<int, int>, int> mp; deque<node> dq; dq.push_back({s1, s2, 0}); while (dq.size()) { auto it = dq.front(); dq.pop_front(); int x = it.x, y = it.y, z = it.z; if (x == t1 && y == t2) { cout << z; return; } if(mp[{x,y}])continue; mp[{x, y}] = 1; for (int j = 1; j <= 4; j++) { int p = a[y][j]; int w = j % 4 + 1; if (p == x) { if (mp[{y, a[y][w]}] || a[y][w] == 0) continue; dq.push_front({y, a[y][w], z}); } else { if (mp[{y, a[y][w]}] || a[y][w] == 0) continue; dq.push_back({y, a[y][w], z + 1}); } } } cout << -1 << endl; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr); memset(h, -1, sizeof h); cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= 4; j++) { cin >> a[i][j]; if (!a[i][j]) continue; add(i, a[i][j]); add(a[i][j], i); } cin >> s1 >> s2 >> t1 >> t2; bfs(); return 0; }
这篇关于牛客多校补题3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?