QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#687466 | #8236. Snake Move | asitshouldbe | RE | 0ms | 0kb | C++20 | 5.4kb | 2024-10-29 19:11:00 | 2024-10-29 19:11:00 |
answer
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#define x first
#define y second
#define endl '\n'
#define pi acos(-1.0)
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<int, PII> PIII;
typedef pair<PII, char> PIIC;
typedef long long LL;
int dx[] = {1, 0, 0, -1, -1, -1, 1, 1}, dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
int mou[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int N = 3e3 + 10, M = 50 + 10, mod = 998244353, INF = 0x3f3f3f3f;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
int n, m,k, t,body[N][N];
string g[N];
int d[N][N];
bool st[N][N];
template <typename T>
inline T read()
{
T x = 0;
int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
LL qmi(LL a, LL b)
{
LL ans = 1 % mod;
while (b)
{
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
LL inv(int x)
{
return qmi(x, mod - 2);
}
LL Random(LL mod)
{
LL res = INT32_MAX;
return res * rand() * rand() % mod;
}
int sgn(double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
else return 1;
}
struct Point
{
double x, y;
Point() {}
Point(double _x, double _y) { x = _x;y = _y; }
bool operator==(Point b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
bool operator<(Point b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
// 叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
// 点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
// 数乘
Point operator*(const double &k) const {return Point(x * k, y * k);}
Point operator/(const double &k) const { return Point(x / k, y / k);}
};
struct Line
{
Point s, e;
Line() {}
Line(Point _s, Point _e) { s = _s;e = _e; }
// ax+by+c=0
Line(double a, double b, double c)
{
if (sgn(a) == 0)
{
s = Point(0, -c / b);
e = Point(1, -c / b);
}
else if (sgn(b) == 0)
{
s = Point(-c / a, 0);
e = Point(-c / a, 1);
}
else
{
s = Point(0, -c / b);
e = Point(1, (-c - a) / b);
}
}
//`直线和线段相交判断`
int linecrossseg(Line v)
{
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2) return 2; //`2 规范相交`
return (d1 == 0 || d2 == 0); //`1 非规范相交 0 不相交`
}
//`两向量平行(对应直线平行或重合)`
bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
//`点在线段上的判断`
bool pointonseg(Point p) { return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0; }
//`求两直线的交点 要保证两直线不平行或重合`
Point crosspoint(Line l)
{
Point u = e - s, v = l.e - l.s;
double t = (s - l.s) ^ v / (v ^ u);
return s + u * t;
}
int relation(Point p)
{
int c = sgn((p - s) ^ (e - s));
if (c < 0) return 1; //`1 在左侧`
else if (c > 0) return 2; //`2 在右侧`
else return 3; //`3 在直线上`
}
};
bool solve()
{
priority_queue<PIII,vector<PIII>,greater<PIII>>heap;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) d[i][j]=INF;
for(int i=0;i<k;i++){
int x,y;cin>>x>>y;
--x,--y;
body[x][y]=k-i;
if(!i){
d[x][y]=0;
heap.push({0,{x,y}});
}
}
// for(int i=0;i<n;i++,puts(""))
// for(int j=0;j<m;j++) cout<<body[i][j]<<" ";
for(int i=0;i<n;i++) cin>>g[i];
while(heap.size()){
auto t=heap.top();heap.pop();
int dis=t.x,x=t.y.x,y=t.y.y;
if(st[x][y]) continue;
st[x][y]=1;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=n||b<0||b>=m||g[a][b]=='#'||st[a][b]) continue;
if(d[a][b]>max(dis+1,body[a][b])){
d[a][b]=max(dis+1,body[a][b]);
heap.push({d[a][b],{a,b}});
}
}
}
// for(int i=0;i<n;i++,puts(""))
// for(int j=0;j<m;j++) cout<<d[i][j]<<" ";
LL res=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(d[i][j]!=inf) res+=(LL)d[i][j]*d[i][j];
cout<<res;
}
int main()
{
//clock_t start,end;//定义clock_t变量
//start = clock();
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0),cout.precision(10);
// freopen("in.in","r",stdin);
// freopen("order.in","w",stdout);
t = 1; //cin >> t;
while (t--) solve();
//end = clock(); //结束时间
//cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....