AcWing 5590. 沿栅栏散步
原题链接
简单
作者:
懒惰的蚩蚩
,
2024-11-01 21:09:52
,
所有人可见
,
阅读 526
模拟
最重要的是,将栅栏处理成从1开始点数就可以了,如果实在不明白可以输出一下我处理之后的栅栏。
1 8 7
2 0 6
3 4 5
因为是一个闭环,所以只有两条路可以走。
分别计算一下,两条路的最短距离就可以了。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 15, M = 2e5 + 15;
typedef pair<int, int> PII;
int g[N][N];
PII lan[M];
int idx = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, p, x1, y1, x2, y2;
cin >> n >> p;
for(int i = 1; i <= p; i++) {
cin >> x1 >> y1;
lan[i] = {x1, y1};
}
for(int i = 2; i <= p; i++) {
int a1 = lan[i - 1].first;
int b1 = lan[i - 1].second;
int a2 = lan[i].first;
int b2 = lan[i].second;
if(a1 != a2 && b1 == b2) {
if(a1 < a2) {
for(int i = a1; i <= a2; i++) {
if(g[i][b1] == 0) g[i][b1] = idx++;
}
}else if(a1 > a2) {
for(int i = a1; i >= a2; i--) {
if(g[i][b1] == 0) g[i][b1] = idx++;
}
}
}else if(a1 == a2 && b1 != b2) {
if(b1 < b2) {
for(int i = b1; i <= b2; i++) {
if(g[a1][i] == 0) g[a1][i] = idx++;
}
}else if(b1 > b2) {
for(int i = b1; i >= b2; i--) {
if(g[a1][i] == 0) g[a1][i] = idx++;
}
}
}
}
int a1 = lan[p].first;
int b1 = lan[p].second;
int a2 = lan[1].first;
int b2 = lan[1].second;
if(a1 != a2 && b1 == b2) {
if(a1 < a2) {
for(int i = a1; i <= a2; i++) {
if(g[i][b1] == 0) g[i][b1] = idx++;
}
}else if(a1 > a2) {
for(int i = a1; i >= a2; i--) {
if(g[i][b1] == 0) g[i][b1] = idx++;
}
}
}else if(a1 == a2 && b1 != b2) {
if(b1 < b2) {
for(int i = b1; i <= b2; i++) {
if(g[a1][i] == 0) g[a1][i] = idx++;
}
}else if(b1 > b2) {
for(int i = b1; i >= b2; i--) {
if(g[a1][i] == 0) g[a1][i] = idx++;
}
}
}
int sum = idx - 1;
while(n--) {
cin >> x1 >> y1 >> x2 >> y2;
int ft = (g[x2][y2] - g[x1][y1] + sum) % sum;
int ans = min(ft, sum - ft);
cout << ans << endl;
}
return 0;
}
对楼主的代码做个小优化。在进行模拟移动之前,将第一个起始点放到最后作为终点。最后可以免于重复的代码
#include <iostream> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = 200010; int n, p; int g[N][N]; int dis[N][N]; PII pil[M]; int main() { scanf("%d%d", &n, &p); for(int i = 0; i < p; i ++) scanf("%d%d", &pil[i].x, &pil[i].y); pil[p].x = pil[0].x, pil[p].y = pil[0].y;//优化,将第一个点放到最后作为结尾,形成一个环 long long sum = 0; PII last = pil[0];//初始木桩为第一个木桩 for(int i = 1; i <= p; i ++) { if(pil[i].x == last.x)//纵向栅栏 { if(pil[i].y > last.y)//向上迭代距离 for(int j = last.y + 1; j <= pil[i].y; j ++) dis[last.x][j] = sum ++; else if (pil[i].y < last.y)//向下迭代距离 for(int j = last.y - 1; j >= pil[i].y; j --) dis[last.x][j] = sum ++; } if(pil[i].y == last.y)//横向栅栏 { if(pil[i].x > last.x)//向右迭代距离 for(int j = last.x + 1; j <= pil[i].x; j ++) dis[j][last.y] = sum ++; else if(pil[i].x < last.x)//向左迭代距离 for(int j = last.x - 1; j >= pil[i].x; j --) dis[j][last.y] = sum ++; } last = pil[i];//更新木桩 } while (n -- ) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); long long distance1 = abs(dis[a][b] - dis[c][d]); long long distance2 = sum - distance1; if(distance1 <= distance2) printf("%lld\n", distance1); else printf("%lld\n", distance2); } }
tql,不过有点好奇为什么sum是从0开始,这样子写不应该从1开始么?
sum表示的是从起始点到路线上的点的距离,初始的时候奶牛在起始点,起始点到起始点的距离为0
但是你是在dis[last.x][last.y + 1]这个地方给赋值sum时sum是等于0的,这里不是起始点哦
写的时间有点久了,我再看看
我嘞个豆,学姐好厉害,orz..