QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#664557 | #8236. Snake Move | chenkaiwen | TL | 1ms | 7800kb | C++14 | 2.4kb | 2024-10-21 21:11:07 | 2024-10-21 21:11:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
__int128 Read() {
__int128 w=0,f=1;
char c=getchar();
while(c>'9'||c<'0') {
if(c=='-')f*=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
string Write(__int128 x) {
string s="";
bool f=0;
if(x<0)f=1,x=x*-1;
while(x) {
s=(char)(x%10+'0')+s;
x=x/10;
}
if(!s.size())s="0";
return (f?"-":"")+s;
}
#define int long long
int n,m,k;
string s[3030];
__int128 dis[3030][3030];
int sk[3030][3030];
struct as {
int x,y,d;
};
const int FX[4]= {0,0,1,-1},FY[4]= {1,-1,0,0};
#define D(X) dis[X.x][X.y]
#define T(X,i,ds) ((as){X.x+FX[i],X.y+FY[i],ds})
#define S(X) ((bool)(s[X.x][X.y]=='.'))
queue<as>q1,q2;
bool vis[3030][3030];
void DIJ(as rt) {
for(int i=0; i<=n+1; i++)for(int j=0; j<=m+2; j++)dis[i][j]=1e9+7;
// cout<<"QAQ\n";
D(rt)=0;
q1.push(rt);
while(q1.size()||q2.size()) {
// cout<<"QAQ1\n";
as u,v;
if(q1.size()&&q2.size()) {
if(D(q1.front())<D(q2.front())) {
u=q1.front();
q1.pop();
} else {
u=q2.front();
q2.pop();
}
} else {
if(q1.size()) {
u=q1.front();
q1.pop();
} else {
u=q2.front();
q2.pop();
}
}
// if(u.d!=D(u))continue;
if(vis[u.x][u.y])continue;
vis[u.x][u.y]=0;
// cout<<u.x<<" "<<u.y<<endl;
for(int i=0; i<4; i++) {
v=T(u,i,0);
if(!S(v))continue;
if(sk[v.x][v.y]) {
if(D(v)>max(D(u)+1ll,(__int128)(k-sk[v.x][v.y]+1))) {
D(v)=max(D(u)+1ll,(__int128)(k-sk[v.x][v.y]+1));
v.d=D(v);
if(!vis[v.x][v.y])q2.push(v);
}
} else {
if(D(v)>D(u)) {
D(v)=D(u)+1;
v.d=D(v);
// if(!vis[v.x][v.y])
if(!vis[v.x][v.y])q1.push(v);
}
}
}
}
}
int stx,sty;
void Work() {
cin>>n>>m>>k;
for(int i=1; i<=k; i++) {
int t1,t2;
cin>>t1>>t2;
sk[t1][t2]=i;
if(i==1)stx=t1,sty=t2;
}
for(int i=1; i<=n; i++) {
cin>>s[i];
s[i]="#"+s[i]+"#";
}
for(int i=0; i<=m+1; i++)s[0]=s[0]+"#",s[n+1]=s[n+1]+"#";
// for(int i=0; i<=n+1; i++)cout<<s[i]<<endl;
DIJ((as) {
stx,sty,0
});
__int128 ans=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++){
if(dis[i][j]>1e9)dis[i][j]=0;
// cout<<dis[i][j]<<" ";
ans+=dis[i][j]*dis[i][j];
}
// cout<<"\n";
}
cout<<Write(ans)<<endl;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
Work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7796kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7800kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Time Limit Exceeded
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................