QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376310 | #8236. Snake Move | ir101 | WA | 1ms | 8124kb | C++20 | 1.8kb | 2024-04-04 03:40:39 | 2024-04-04 03:40:39 |
Judging History
answer
# pragma GCC optimize(2)
#include <iostream>
#include <queue>
const int mod=1e9+7;
#define ll long long
using namespace std;
#define endl '\n'
//learning
#define PII pair<int,int>
const int N=3e3+5;
int f[N][N];
int extra_dis[N][N];
char g[N][N];
int n,m,k;
int stx,sty;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
void solve(){
scanf("%d %d %d",&n,&m,&k);
for (int i = 1; i <=k ; ++i) {
int x,y;
scanf("%d %d",&x,&y);
if(i==1){
stx=x,sty=y;
}
extra_dis[x][y]=k-i;
}
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=m ; ++j) {
scanf("%c",&g[i][j]);
f[i][j]=1e9;
}
}
queue<PII>q;
q.push({stx,sty});
f[stx][sty]=0;
while (!q.empty()){
auto [x,y]=q.front();
q.pop();
for (int i = 0; i <4 ; ++i) {
int xx=x+dx[i],yy=y+dy[i];
if(xx<1 or xx>n or yy<1 or yy>m or g[xx][yy]=='#')continue;
if(!extra_dis[xx][yy]){
if(f[xx][yy]>f[x][y]+1){
f[xx][yy]=f[x][y]+1;
q.push({xx,yy});
}
}
else{
if(f[xx][yy]>f[x][y]+max(0,extra_dis[xx][yy]-f[x][y])+1) {
f[xx][yy] = f[x][y] + max(0, extra_dis[xx][yy] - f[x][y]) + 1;
q.push({xx, yy});
}
}
}
}
unsigned ll ans=0;
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=m ; ++j) {
if(f[i][j]==1e9){
continue;
}
ans+=(unsigned ll)f[i][j]*f[i][j];
}
}
printf("%lld",ans);
}
int32_t main() {
int t=1;
while (t--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7884kb
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: 8124kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7876kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
218
result:
wrong answer 1st lines differ - expected: '407', found: '218'