P7473 重力球

2023-10-28 06:15
文章标签 重力 p7473

本文主要是介绍P7473 重力球,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P7473 重力球

Solution

考虑 Brute Force:对于每一次询问,通过 BFS 处理出最近的交汇点,输出答案。

很显然,会 TLE \colorbox{navy}{\color{white}{TLE}} TLE

故,考虑 优化

观察发现障碍物数量非常少,故设状态 ( x , y , d ) \mathrm{(x,y,d)} (x,y,d) 表示第 1 1 1 个小球被第 x x x 个障碍物卡住,第 2 2 2 个小球被第 y y y 个小球卡住,在障碍物的 d d d 方向(如图)。此时,发现总共的状态数量不多。

这样我们就可以用着 3 3 3 个数来确定出每个小球的位置。

之后,考虑每一次走一定是走到一个 障碍物四周 的点,所以可以提前预处理,记作 T o i , j , k \mathrm{To_{i,j,k}} Toi,j,k 表示 ( i , j ) (i,j) (i,j) k k k 方向会走到的点。

对于任意两个起点,需要向四周可到达的点连边:

假设当前是 x 1 , y 1 , d \mathrm{x_1,y_1,d} x1,y1,d,方向是 2 2 2,那么运动之后, d = d ⊕ 2 \mathrm{d=d\oplus 2} d=d2(即原来在上面,变成下面;原来在左边,变成右边…… 通过上图观察发现异或 2 2 2 可以解决);点会变为 T o x 1 , y 1 , 2 \mathrm{To_{x_1,y_1,2}} Tox1,y1,2

依此建边即可。


预处理操作结束之后,对于每一个询问:

  1. 直接 BFS 算出终点为哪个点最近(易 T L E \mathrm{TLE} TLE
  2. 正难则反,考虑对于所有可能终点中到这两个点的最短距离,这其实就是一个 多源BFS!注意:使用该方法需建反边!

建议采取第 2 2 2 种操作,当然这样并不需要每一次都进行 BFS,只需提前做 1 1 1 次即可。

由于,每一次询问的时候,不一定是在一个 障碍物四周,所以需要上、下、左、右四个方向,跑到障碍物四周,然后取最小值即可。


Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>using namespace std;typedef pair<int, int> PII;
typedef long long LL;const int SIZE = 255;int N, M, Q;
vector<PII> Obstackle;
int Is[SIZE][SIZE], Id[SIZE][SIZE], cnt;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int To[SIZE][SIZE][4], Dist[SIZE * 5][SIZE * 5][4];
struct P
{int x, y, d;
};
std::vector<P> G[SIZE * 5][SIZE * 5][4];
int Vis[SIZE * 5][SIZE * 5][4];bool check(int x, int y)
{return x >= 1 && y >= 1 && x <= N && y <= N && !Is[x][y];
}void Init()
{for (int i = 1; i <= N; i ++)for (int j = 1; j <= N; j ++)for (int k = 0; k < 4; k ++){int x = i, y = j;while (!Is[x][y])x += dx[k], y += dy[k];To[i][j][k] = Id[x][y];}for (auto i : Obstackle)for (auto j : Obstackle)for (int sd = 0; sd < 4; sd ++)for (int k = 0; k < 4; k ++){int x1 = i.first + dx[k], y1 = i.second + dy[k], x2 = j.first + dx[k], y2 = j.second + dy[k];if (check(x1, y1) && check(x2, y2)){int To1 = To[x1][y1][sd], To2 = To[x2][y2][sd];G[To1][To2][sd ^ 2].push_back({Id[i.first][i.second], Id[j.first][j.second], k});}}
}void BFS()
{memset(Dist, 0x3f, sizeof Dist);queue<P> Q;for (auto c : Obstackle)for (int i = 0; i < 4; i ++){int id = Id[c.first][c.second];int x = c.first + dx[i], y = c.second + dy[i];if (check(x, y))Dist[id][id][i] = 0, Q.push({id, id, i});}while (Q.size()){auto Tmp = Q.front();Q.pop();if (Vis[Tmp.x][Tmp.y][Tmp.d]) continue;Vis[Tmp.x][Tmp.y][Tmp.d] = 1;for (auto c : G[Tmp.x][Tmp.y][Tmp.d])if (Dist[c.x][c.y][c.d] > Dist[Tmp.x][Tmp.y][Tmp.d] + 1){Q.push(c);Dist[c.x][c.y][c.d] = min(Dist[c.x][c.y][c.d], Dist[Tmp.x][Tmp.y][Tmp.d] + 1);}}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> N >> M >> Q;for (int i = 1; i <= M; i ++){int x, y;cin >> x >> y;Id[x][y] = ++ cnt;Is[x][y] = 1;Obstackle.push_back({x, y});}for (int i = 0; i <= N + 1; i ++)for (int j = 0; j <= N + 1; j ++)if (!i || !j || i > N || j > N){Id[i][j] = ++ cnt;Is[i][j] = 1;Obstackle.push_back({i, j});}Init();BFS();while (Q --){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int Result = 2e9;for (int i = 0; i < 4; i ++)Result = min(Result, Dist[To[x1][y1][i]][To[x2][y2][i]][i ^ 2] + 1);if (x1 == x2 && y1 == y2) Result = 0;if (Result >= 1e9) Result = -1;cout << Result << endl;}return 0;
}

这篇关于P7473 重力球的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/291262

相关文章

【无线通信发展史⑧】测量地球质量?重力加速度g的测量?如何推导单摆周期公式?地球半径R是怎么测量出来的?

前言:用这几个问答形式来解读下我这个系列的来龙去脉。如果大家觉得本篇文章不水的话希望帮忙点赞收藏加关注,你们的鼓舞是我继续更新的动力。 我为什么会写这个系列呢? 首先肯定是因为我本身就是一名从业通信者,想着更加了解自己专业的知识,所以更想着从头开始了解通信的来源以及在每一个时代的发展进程。 为什么会从头开始写通信? 我最早是学习了中华上下五千年,应该说朝代史,这个算个人兴趣,从夏

cocos2d-x 重力感应

本文没你想象的那么,,复杂。其实就是通过重力感应控制个小球移动而已。 先看头文件: [cpp] view plain copy #ifndef __HELLOWORLD_SCENE_H__  #define __HELLOWORLD_SCENE_H__    #include "cocos2d.h"  USING_NS_CC;    class HelloWorld : public

Egret:重力感应

class MotionExample extends egret.DisplayObjectContainer {label: egret.TextField;motion: egret.Motion;constructor() {super();//文本框this.label = new egret.TextField();this.label.y = 400;this.label.

cocos重力感应

采用重力加速度感应控制屏幕旋转最为理想。 不方便作图,简单说:重力加速度感应可以想象成一个小球在坐标系中,三个方向上的加速度。永远以手机屏幕为准,不以外界为准作图,手机水平放置,向上是y轴正向,向右是x轴正向,向外是z轴正向。这和高数坐标系一样。 注意:你移动手机反映在坐标系上你移动的是坐标系远点(旋转)   1. Accelrator的x,y,z轴的正负向变化:

Python重力弹弓流体晃动微分方程模型和交直流电阻电容电路

🎯要点 🎯计算地球大气层中热层金属坠物运动轨迹 | 🎯计算炮弹最佳弹射角度耦合微分方程 | 🎯计算电磁拉莫尔半径螺旋运动 | 🎯计算航天器重力弹弓运动力学微分方程 | 🎯计算双摆的混沌运动非线性微分方程,绘制相空图 | 🎯计算绝热和无粘流流体力学微分方程 | 🎯计算容器流体晃动自由表面简谐运动数学模型 | 🎯计算化学物质的伦纳德-琼斯势物理模型 | 🎯分析直流交流电阻电容电路

android 重力感应

注意:你移动手机反映在坐标系上你移动的是坐标系远点(旋转)   1. Accelrator的x,y,z轴的正负向变化:   手机屏幕向上水平放置时: (x,y,z) = (0, 0, -9.81)   当手机顶部抬起时: y减小,且为负值   当手机底部抬起时: y增加,且为正值   当手机右侧抬起时: x减小,且为负值   当手机左侧抬起时: x增加,且为正值   2. Acce

小球垂直跳动,C语言模拟重力加速度

位移公式 1、速度和时间关系: 2、位移和时间关系: 3、力和加速度关系: 4、空气阻力: 受理分析 以向下运动为正方向 1、向下运动整体受力,重力加空气阻力: 2、向上运动整理受力,重力减空气阻力: 代码实现 #include <stdio.h>#define GRAVITY_RATIO 9.8f#define HALF_CPS_K 0.1f #defin

Python对头发二维建模(考虑风力、重力)

目录 一、背景 二、代码 一、背景 数值方法被用于创建电影、游戏或其他媒体中的计算机图形。例如,生成“逼真”的烟雾、水或爆炸等动画。本文内容是对头发的模拟,要求考虑重力、风力的影响。 假设: 1、人的头部是一个半径为10厘米的球体。 2、每根头发都与球体的表面垂直相交。 3、作用在每根头发上的力包括重力(在-z方向上)和恒定的风力(在+x方向上)。 二、代码 #导入pytho

课题学习(二十)----阅读《近钻头井斜动态测量重力加速度信号提取方法研究》论文

摘要:利用加速度计进行近钻头井斜动态测量时, 钻具的高速旋转、 井下强振动、强冲击环境给重力加速度测量带来极大干扰,如何从干扰噪声中有效提取重力加速度信号对于提高井斜角和工具面角的测量精度至关重要。 根据重力加速度径向和切向分量为周期性信号,轴向分量为近似直流信号,离心加速度为缓慢变化信号, 振动和冲击加速度为随机信号的特征,提出一种基于互相关检测的重力加速度信号提取方法,选择径向或切向磁力

Android根据重力感应选装方向,四个方向都支持

不废话,直接上源码: 辅助工具类ChangeOrientationHandler.java public class ChangeOrientationHandler extends Handler {private Activity activity;public ChangeOrientationHandler(Activity ac) {super();activity = ac;}@O