QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#687473 | #8236. Snake Move | asitshouldbe | RE | 0ms | 0kb | C++20 | 2.4kb | 2024-10-29 19:12:16 | 2024-10-29 19:12:16 |
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];
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....