深圳-第三期-XP03A-一班-day2
2026-08-03 20:51:27
发布于：广东
91阅读
0回复
0点赞
day2
pair 与 array
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
char g[15][15];
ll dis[15][15];
// dis[x][y] 表示从起点 -> (x,y)的距离
// 规定起点距离起点为 1：dis[1][1] = 1
/**
* T1 表示一种类型
* T2 表示一种类型
* pair<T1, T2> p;
*
* 相当于结构体：
* struct Node {
* T1 first;
* T2 second;
* } p;
*
* pair<ll, string> p;
*
* 相当于结构体：
* struct Node {
* ll first;
* string second;
* } p;
* bool cmp(Node x, Node y) {
* if (x.first != y.first) return x.first < y.first;
* return x.second < y.second;
* }
*
*
* 定义一个长度为 2 的数组：
* pair<ll, ll> p;
* array<ll, 2> a; -> ll a[2]
*
* 获取第一个元素：
* p.first
* a[0]
*
* 获取第二个元素：
* p.second
* a[1]
*
*/
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) {
for (ll j = 1; j <= m; j ++) {
cin >> g[i][j];
}
}
queue< pair<ll, ll> > qu;
return 0;
}
T112340.逃离迷宫2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
char g[15][15];
ll dis[15][15];
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
// dis[x][y] 表示从起点 -> (x,y)的距离
// 规定起点距离起点为 1：dis[1][1] = 1
/**
* T1 表示一种类型
* T2 表示一种类型
* pair<T1, T2> p;
*
* 相当于结构体：
* struct Node {
* T1 first;
* T2 second;
* } p;
*
* pair<ll, string> p;
*
* 相当于结构体：
* struct Node {
* ll first;
* string second;
* } p;
* bool cmp(Node x, Node y) {
* if (x.first != y.first) return x.first < y.first;
* return x.second < y.second;
* }
*
*
* 定义一个长度为 2 的数组：
* pair<ll, ll> p;
* array<ll, 2> a; -> ll a[2]
*
* 获取第一个元素：
* p.first
* a[0]
*
* 获取第二个元素：
* p.second
* a[1]
*
*/
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) {
for (ll j = 1; j <= m; j ++) {
cin >> g[i][j];
}
}
// 第一步：定义队列
// 第二步：起点入队
// 第三步：立即标记为已访问的状态，立即计算最短路
queue< pair<ll, ll> > qu;
qu.push({1, 1});
dis[1][1] = 1;
// 只要队列不为空，就不断执行循环的过程
while (qu.size()) { // while (!qu.empty())
// 把队头元素取出来
// 判断是否搜索到终点（第一次走到一定是最短的）
// auto 叫做：自动类型推导，根据右边具体的值来推导变量类型
auto nd = qu.front(); qu.pop();
ll x = nd.first, y = nd.second;
if (x == n && y == m) {
cout << dis[x][y] - 1 << '\n';
return 0;
}
// 搜索所有的邻居（往邻居方向扩展延伸）
for (ll i = 0; i < 4; i ++) {
ll nx = x + dx[i];
ll ny = y + dy[i];
// 扩展邻居的一个前提是：邻居是合法的，并且没有访问过的
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (g[nx][ny] == '#') continue;
if (dis[nx][ny]) continue;
// 新点入队
// 立即标记为已访问，立即计算最短路
qu.push({nx, ny});
dis[nx][ny] = dis[x][y] + 1;
}
}
cout << -1;
return 0;
}
T109677.小试牛刀
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
vector<ll> g[110];
ll start;
ll dis[110];
int main() {
cin >> n >> m;
for (ll i = 1; i <= m; i ++) {
ll u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> start;
// 定义队列
// 起点入队
// 立即标记为已访问，立即记录最短路
queue<ll> qu;
qu.push(start);
dis[start] = 1;
// 只要队列不为空，就不断的执行循环的过程
while (qu.size()) {
// 把队头元素拿出来
ll x = qu.front(); qu.pop();
// 往周围所有的方向搜索（往邻居扩展）
// x 的邻居都存放在：g[x] 这个 vector 中
for (ll y : g[x]) {
// y 就是 x 的某个邻居
// y 如果要进入队列的话，必须得保证
// y 是合法的，没有访问过的
if (dis[y]) continue;
// 入队
// 立即标记为已访问，立即计算最短路
qu.push(y);
dis[y] = dis[x] + 1;
}
}
for (ll i = 1; i <= n; i ++) {
cout << dis[i] - 1 << " ";
}
return 0;
}
T112336.充满希望的骑士与棋盘
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, x, y;
ll dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
ll dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
ll dis[1010][1010];
int main() {
cin >> n >> m >> x >> y;
queue< pair<ll, ll> > qu;
qu.push( {x, y} );
dis[x][y] = 1;
while (qu.size()) {
pair<ll, ll> nd = qu.front(); qu.pop();
ll x = nd.first, y = nd.second;
for (ll i = 0; i < 8; i ++) {
ll nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (dis[nx][ny]) continue;
qu.push({nx, ny});
dis[nx][ny] = dis[x][y] + 1;
}
}
for (ll i = 1; i <= n; i ++) {
for (ll j = 1; j <= m; j ++) {
cout << dis[i][j] - 1 << " ";
}
cout << '\n';
}
return 0;
}
T112727.连通块问题(BFS)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
ll n, m;
vector<ll> g[N];
ll x, y;
bool vis[N];
ll flag; // flag 判断是否能从 x 走到 y
ll cnt; // cnt 记录从 x 出发的连通块的点的数量
int main() {
cin >> n >> m;
for (ll i = 1; i <= m; i ++) {
ll u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> x >> y;
// 定义队列
// 放入元素，并立即标记为已访问
queue<ll> qu;
qu.push(x);
vis[x] = 1;
while (qu.size()) {
ll u = qu.front(); qu.pop();
if (u == y) flag = 1;
cnt ++;
// 往周围扩展（往邻居扩展）
for (ll v : g[u]) {
if (vis[v]) continue;
qu.push(v);
vis[v] = 1;
}
}
if (flag) cout << cnt << '\n';
else cout << 0 << '\n';
return 0;
}
T109302.彩色墨水扩散
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e3 + 10;
ll n, m;
char g[N][N];
ll dis[N][N];
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
queue< pair<ll, ll> > qu;
ll mx;
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) {
for (ll j = 1; j <= m; j ++) {
cin >> g[i][j];
// 多源头入队列
if (g[i][j] == '#') qu.push({i, j}), dis[i][j] = 1;
}
}
while (qu.size()) {
auto nd = qu.front(); qu.pop();
ll x = nd.first, y = nd.second;
mx = max(mx, dis[x][y]);
for (ll i = 0; i < 4; i ++) {
ll nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (dis[nx][ny]) continue;
qu.push({nx, ny});
dis[nx][ny] = dis[x][y] + 1;
}
}
cout << mx - 1 << '\n';
return 0;
}
T111991.迷路的小猫
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll n, k;
ll dis[N * 2];
queue<ll> qu;
int main() {
cin >> n >> k;
if (k <= n) {
cout << n - k << '\n';
return 0;
}
qu.push(n);
dis[n] = 1;
while (qu.size()) {
ll x = qu.front(); qu.pop();
if (x == k) {
cout << dis[x] - 1 << '\n';
return 0;
}
ll nx[] = {x - 1, x + 1, 2 * x};
for (ll y : nx) {
if (y < 0 || y > 2e5) continue;
if (dis[y]) continue;
qu.push(y);
dis[y] = dis[x] + 1;
}
}
return 0;
}
T109459.神秘跳跃石板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 210;
ll n, A, B;
ll k[N];
ll dis[N];
queue<ll> qu;
int main() {
cin >> n >> A >> B;
for (ll i = 1; i <= n; i++) cin >> k[i];
qu.push(A); dis[A] = 1;
while (qu.size()) {
ll x = qu.front(); qu.pop();
if (x == B) {
cout << dis[x] - 1 << '\n';
return 0;
}
ll nx[] = {x - k[x], x + k[x]};
for (ll y : nx) {
if (y < 1 || y > n) continue;
if (dis[y]) continue;
qu.push(y); dis[y] = dis[x] + 1;
}
}
cout << -1 << '\n';
return 0;
}
T109458.单词接龙
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* map<下标的类型, 值的类型> dis;
* map<string, ll> dis;
* // dis[string] = ll; // 时间复杂度是：log(n)
* 普通的数组 dis[i] = ll; // 时间复杂度是：O(1)
*/
string A, B;
ll n;
string a[5010];
queue<string> qu;
map<string, ll> dis;
int main() {
cin >> A >> B;
cin >> n;
for (ll i = 1; i <= n; i ++) cin >> a[i];
qu.push(A);
dis[A] = 1;
while (qu.size()) {
string s = qu.front(); qu.pop();
if (s == B) {
cout << dis[s] << '\n';
return 0;
}
for (ll i = 1; i <= n; i ++) {
ll cnt = 0;
for (ll j = 0; j < s.size(); j ++) if (s[j] != a[i][j]) cnt ++;
if (cnt == 1) {
if (dis[a[i]]) continue;
qu.push(a[i]);
dis[a[i]] = dis[s] + 1;
}
}
}
cout << 0;
return 0;
}
部落中的最强战士
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll n, m;
ll a[N];
vector<ll> g[N];
ll vis[N];
vector< vector<ll> > vt;
ll ans[N];
void bfs(ll u) {
queue<ll> qu;
qu.push(u);
vis[u] = 1;
while (qu.size()) {
ll u = qu.front(); qu.pop();
vt.back().push_back(u);
for (ll v : g[u]) {
if (vis[v]) continue;
qu.push(v);
vis[v] = 1;
}
}
}
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) cin >> a[i];
for (ll i = 1; i <= m; i ++) {
ll u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 连通块可能很多个
for (ll i = 1; i <= n; i ++) {
if (vis[i]) continue;
vt.push_back({}); // 先放入空数组
bfs(i); // 从 i 号点出发，所有经过的点都丢入 vt 的最后一个动态数组中
auto& arr = vt.back();
ll mx = -1e18;
for (ll x : arr) mx = max(mx, a[x]);
for (ll x : arr) ans[x] = mx;
}
for (ll i = 1; i <= n; i ++) cout << ans[i] << ' ';
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll n, m;
pair<ll, ll> a[N];
vector<ll> g[N];
ll vis[N];
ll ans[N];
void bfs(ll u, ll mx) {
queue<ll> qu;
qu.push(u);
vis[u] = 1;
ans[u] = mx;
while (qu.size()) {
ll x = qu.front(); qu.pop();
for (ll y : g[x]) {
if (vis[y]) continue;
qu.push(y);
vis[y] = 1;
ans[y] = mx;
}
}
}
int main() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) {
ll x; cin >> x;
a[i] = {x, i};
}
sort(a + 1, a + n + 1);
for (ll i = 1; i <= m; i ++) {
ll u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (ll i = n; i >= 1; i --) {
ll x = a[i].first, id = a[i].second;
if (vis[id]) continue;
bfs(id, x);
}
for (ll i = 1; i <= n; i ++) cout << ans[i] << " ";
return 0;
}
感染时间
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
ll a, b;
ll dis[1010][1010];
queue<pair<ll, ll>> q;
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
int main() {
cin >> n >> m >> a >> b;
for (ll i = 1; i <= a; i ++) {
ll x, y; cin >> x >> y;
q.push({x, y});
dis[x][y] = 1;
}
while (q.size()) {
auto nd = q.front(); q.pop();
ll x = nd.first, y = nd.second;
for (ll i = 0; i < 4; i ++) {
ll nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (dis[nx][ny]) continue;
q.push({nx, ny});
dis[nx][ny] = dis[x][y] + 1;
}
}
for (ll i = 1; i <= b; i ++) {
ll x, y; cin >> x >> y;
cout << dis[x][y] - 1 << '\n';
}
return 0;
}
连通的图
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n, m;
vector< pair<ll, ll> > g[N];
ll vis[N];
bool bfs(ll mx) {
for (ll i = 1; i <= n; i ++) vis[i] = 0;
queue< ll > q;
q.push(1);
vis[1] = 1;
while (q.size()) {
ll u = q.front(); q.pop();
for (pair<ll, ll> nd : g[u]) {
ll w = nd.first, v = nd.second;
if (w > mx) break;
if (vis[v]) continue;
q.push(v);
vis[v] = 1;
}
}
for (ll i = 1; i <= n; i ++) {
if (vis[i] == 0) return false;
}
return true;
}
void solve() {
cin >> n >> m;
for (ll i = 1; i <= n; i ++) g[i].clear();
for (ll i = 1; i <= m; i ++) {
ll u, v, w; cin >> u >> v >> w;
g[u].push_back({w, v});
g[v].push_back({w, u});
}
for (ll i = 1; i <= n; i ++) sort(g[i].begin(), g[i].end());
ll l = 1, r = 1e9;
while (l < r) {
ll mid = (l + r) / 2;
if (bfs(mid)) r = mid;
else l = mid + 1;
}
cout << l;
}
int main() {
ll t; cin >> t; while (t --) solve();
return 0;
}
这里空空如也
有帮助，赞一个