QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661521 | #8236. Snake Move | Lemon | WA | 1058ms | 949648kb | C++14 | 2.6kb | 2024-10-20 16:38:25 | 2024-10-20 16:38:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=8e7;
const int N=9e6;
const ll inf=1e18;
int hd[N],cnt,n,m,k,stx,sty,vis[9000005];
char s[3005][3005];
ll dis[9000005],len[9000005];
ll ans;
struct edge{
int u,to,nxt;
}e[maxn];
void add(int u,int v){
e[++cnt].nxt=hd[u];
e[cnt].to=v;
e[cnt].u=u;
hd[u]=cnt;
}
int pos(int x,int y){
return (x-1)*m+y;
}
queue<int>q;
void bfs(int x,int y){
q.push(pos(x,y));
vis[pos(stx,sty)]=1;
dis[pos(stx,sty)]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>=max(dis[u]+1,len[v]+1)){
dis[v]=max(dis[u]+1,len[v]+1);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dis[pos(i,j)]=inf;
//cout<<pos(i,j)<<' ';
}
//cout<<endl;
}
//cout<<f[1][1]<<endl;
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
if(i==1) stx=x,sty=y;
//p[x][y]=1;
//len[x][y]=k-i+1;
len[pos(x,y)]=k-i;
}
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//cout<<s[i][j]<<' ';
//if(p[i][j]) s[i][j]='#';
if(s[i][j]=='#') continue;
if(s[i-1][j]=='.'){
add(pos(i,j),pos(i-1,j));
add(pos(i-1,j),pos(i,j));
}
if(s[i][j-1]=='.'){
add(pos(i,j),pos(i,j-1));
add(pos(i,j-1),pos(i,j));
}
if(s[i+1][j]=='.'){
add(pos(i,j),pos(i+1,j));
add(pos(i+1,j),pos(i,j));
}
if(s[i][j+1]=='.'){
add(pos(i,j),pos(i,j+1));
add(pos(i,j+1),pos(i,j));
}
}
//cout<<endl;
}
//cout<<stx<<' '<<sty<<endl;
bfs(stx,sty);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// //dis[pos(i,j)]=max(dis[pos(i,j)],len[i][j]+1);
// //cout<<f[i][j]<<' ';
// cout<<dis[pos(i,j)]<<' ';
// }
// cout<<endl;
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dis[pos(i,j)]==inf) continue;
ans+=(dis[pos(i,j)]*dis[pos(i,j)]);
}
}
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 13896kb
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: 0ms
memory: 13864kb
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: 13948kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 1058ms
memory: 948976kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 731ms
memory: 541600kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 125ms
memory: 326648kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 59ms
memory: 190268kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 946ms
memory: 949648kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: -100
Wrong Answer
time: 732ms
memory: 558744kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749317
result:
wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'