首页 技术 正文
技术 2022年11月19日
0 收藏 323 点赞 4,065 浏览 3281 个字

题意:很复杂的题意,我描述不清楚。

题目链接:http://acm.bnu.edu.cn/bnuoj/contest_show.php?cid=3033

大致是,给定一个起点,一个终点,和一些墙,这些墙是不能越过的,然后一个人他每次走可以往四个方向走,可以加速,可以减速,也可以匀速。

也不一定是四个方向,因为他有一个VX,VY,所以每次走的方向其实都是不固定的,所以的四个方向就是他加速度的方向就是这四个。大家理解就好。

然后要从起点开始,走到终点,问最少需要多少步,而且走到终点的时候速度必须是0。

这道题的搜索部分其实很好想到,BFS开四维记录坐标和当前的VX,VY 。

因为速度有负的,所以我把起始速度开到16 。

然后搜索部分没什么问题了,对于计算几何部分的话,就是一个线段交的模版,没敲错基本上没问题。

CODE:.

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;struct Point {
int x , y ;
Point() {}
Point(int xx ,int yy) : x(xx) , y(yy) {}
};
struct stline {
Point a,b;
} line1,line2;
int n , m ;
int num ;
int sx , sy , ex , ey ;
struct WAll {
int sx , sy , ex ,ey ;
} w[11] ;#define N 64
int dis[N][N][32][32] ;
queue<pair<PII, PII> > qe ;
#define MP(a , b , c , d) mp(mp(a, b) , mp(c , d))
int mx[] = {1 , -1 , 0 ,0 , 0 } ;
int my[] = {0 , 0 , 0 ,1 , -1 } ;
int inmap(int x ,int y) {
if(x >= 0 && x < n && y >= 0 && y < m)return 1 ;
return 0 ;
}int dblcmp(double a,double b) {
if (fabs(a-b)<=1E-6) return 0;
if (a>b) return 1;
else return -1;
}
//***************点积判点是否在线段上***************
double dot(double x1,double y1,double x2,double y2) { //点积
return x1*x2+y1*y2;
}
int point_on_line(Point a,Point b,Point c) { //求a点是不是在线段bc上,>0不在,=0与端点重合,<0在。
return dblcmp(dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y),0);
}
//**************************************************
double cross(double x1,double y1,double x2,double y2) { //叉积
return x1*y2-x2*y1;
}
double ab_cross_ac(Point a,Point b,Point c) { //ab与ac的叉集
return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int ab_cross_cd (Point a,Point b,Point c,Point d) { //求ab是否与cd相交
double s1,s2,s3,s4;
int d1,d2,d3,d4;
Point p;
d1=dblcmp(s1=ab_cross_ac(a,b,c),0);
d2=dblcmp(s2=ab_cross_ac(a,b,d),0);
d3=dblcmp(s3=ab_cross_ac(c,d,a),0);
d4=dblcmp(s4=ab_cross_ac(c,d,b),0);
//如果规范相交则求交点
if ((d1^d2)==-2 && (d3^d4)==-2) {
p.x=(c.x*s2-d.x*s1)/(s2-s1);
p.y=(c.y*s2-d.y*s1)/(s2-s1);
return 1;
}//如果不规范相交
if (d1==0 && point_on_line(c,a,b)<=0) {
p=c;
return 1 ;
}
if (d2==0 && point_on_line(d,a,b)<=0) {
p=d;
return 1 ;
}
if (d3==0 && point_on_line(a,c,d)<=0) {
p=a;
return 1 ;
}
if (d4==0 && point_on_line(b,c,d)<=0) {
p=b;
return 1 ;
}
//如果不相交
return 0;
}int check(int x ,int y ,int xx ,int yy){
Point p1(x ,y) ;
Point p2(xx ,yy) ;
for (int i = 0 ; i < num ; i ++ ){
Point p3(w[i].sx , w[i].sy) ;
Point p4(w[i].ex , w[i].ey) ;
if(ab_cross_cd(p1 , p2 , p3 , p4)) return 1 ;
}
return 0 ;
}
int bfs() {
while(!qe.empty())qe.pop() ;
qe.push(MP(sx , sy , 16 , 16)) ;
for (int i = 0 ; i < N ; i ++ ) {
for (int j = 0 ; j < N ; j ++ ) {
for (int k = 0 ; k < N / 2; k ++ )
for (int x = 0 ; x < N / 2 ; x ++ )
dis[i][j][k][x] = inf ;
}
}
dis[sx][sy][16][16] = 0 ;
while(!qe.empty()) {
pair<PII , PII > tp = qe.front() ;
qe.pop() ;
for (int i = 0 ; i < 5 ; i ++ ) {
int vx = tp.SE.FI + mx[i] - 16 ;
int vy = tp.SE.SE + my[i] - 16 ;
int tx = tp.FI.FI + vx ;
int ty = tp.FI.SE + vy ;
if(inmap(tx ,ty) && vx > -16 && vy > -16 && vx < 16 && vy < 16 && !check(tp.FI.FI ,tp.FI.SE , tx ,ty)) {
if(dis[tx][ty][vx + 16][vy + 16] > dis[tp.FI.FI][tp.FI.SE][vx - mx[i] + 16][vy - my[i] + 16] + 1 ) {
dis[tx][ty][vx + 16][vy + 16] = dis[tp.FI.FI][tp.FI.SE][vx - mx[i] + 16][vy - my[i] + 16] + 1 ;
qe.push(MP(tx , ty , vx + 16, vy + 16)) ;
}
}
}
}
return dis[ex][ey][16][16] ;
}
int main() {
while(cin >> m >> n ) {
cin >> sy >> sx >> ey >> ex ;
cin >> num ;
for (int i = 0 ; i < num ; i ++ )cin >> w[i].sy >> w[i].sx >> w[i].ey >> w[i].ex ;
int fk = bfs() ;
cout << fk << endl;
}
return 0 ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,104
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,581
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,428
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,200
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,835
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,918