QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#669590 | #8236. Snake Move | frankly6# | TL | 1ms | 7888kb | C++17 | 1.8kb | 2024-10-23 19:06:49 | 2024-10-23 19:06:49 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> PII;
const int MX=3030;
const int NX=100010;
const int inf=0x3fffffff;
int N, M, K;
int mp[MX][MX], ans[MX][MX];
bool vis[MX][MX];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
queue<PII> q;
void bfs()
{
while(!q.empty())
{
auto [x,y]=q.front(); q.pop();
for(int i=1;i<=4;i++)
{
int nx=x+dx[i], ny=y+dy[i];
if(mp[nx][ny]==-1) continue;
if(nx<=0||nx>N||ny<=0||ny>M) continue;
int upd=max(ans[x][y]+1,(mp[nx][ny]!=0)*(K-mp[nx][ny]+1));
if(ans[nx][ny]<upd) continue;
ans[nx][ny]=upd;
q.push({nx,ny});
}
}
}
int main()
{
// freopen("testdata.in","r",stdin);
N=read(); M=read(); K=read();
for(int i=1;i<=K;i++)
{
int x=read(), y=read();
mp[x][y]=i;
if(i==1)
{
q.push({x,y});
vis[x][y]=1;
}
}
for(int i=1;i<=N;i++)
{
string s; cin >> s; s=" "+s;
for(int j=1;j<=M;j++)
{
if(s[j]=='#') mp[i][j]=-1;
if(!vis[i][j]) ans[i][j]=inf;
}
}
bfs();
ull sum=0;
for(int i=1;i<=N;i++)
{
// cout << "i=" << i << '\n';
for(int j=1;j<=M;j++)
{
// cout << ans[i][j] << " ";
if(ans[i][j]!=inf) sum+=ans[i][j]*ans[i][j];
}
// cout << '\n';
}
cout << sum << '\n';
return (0-0);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7680kb
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: 7680kb
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: 1ms
memory: 7888kb
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 ........................................................................................................#................................................................................................................................................................#................