QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68321#4788. GravityA_zjzjML 217ms163348kbC++141.3kb2022-12-15 19:47:032022-12-15 19:47:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-15 19:47:06]
  • 评测
  • 测评结果:ML
  • 用时:217ms
  • 内存:163348kb
  • [2022-12-15 19:47:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=2e3+10,M=N*N;
int n,m,k,d[N][N],id[N][N],f[M];bool vis[M];char a[N][N],b[N][N];vector<pair<int,int> >A[M];
void dfs(int x,int y){
	if(id[x][y])return;id[x][y]=k;
	if(a[x+1][y]=='#')dfs(x+1,y);if(a[x][y+1]=='#')dfs(x,y+1);
	if(a[x-1][y]=='#')dfs(x-1,y);if(a[x][y-1]=='#')dfs(x,y-1);
}
void add(int u,int v,int w){A[u].push_back({v,w});}
void dij(){
	priority_queue<pair<int,int> >q;q.push({f[0]=0,0});for(int u;!q.empty();){
		u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;
		for(auto [v,w]:A[u])if(f[v]>f[u]+w)f[v]=f[u]+w,q.push({-f[v],v});
	}
}
int main(){
	scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
	memset(f,0x3f,sizeof f);for(int j=1;j<=m;j++)d[n+1][j]=n+1;
	for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)if(a[i][j]=='#')d[i][j]=i;else d[i][j]=d[i+1][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#'&&!id[i][j])k++,dfs(i,j);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')add(id[d[i+1][j]][j],id[i][j],d[i+1][j]-i-1);
	dij();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]='.';
//	for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++)printf("%d ",f[id(i,j)]);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='#')b[i+f[id[i][j]]][j]='#';
	for(int i=1;i<=n;i++)printf("%s\n",b[i]+1);return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 21ms
memory: 114056kb

input:

10 10
..........
..######..
..#....#..
..#.#..#..
..#..#.#..
..#....#..
..######..
..........
..#....#..
.......#..


output:

..........
..........
..######..
..#....#..
..#....#..
..#....#..
..#.##.#..
..######..
.......#..
..#....#..

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 217ms
memory: 163348kb

input:

1583 1799
#..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...

output:

...............................................................................................................................................................................................................................................................................................................

result:

ok 1583 lines

Test #3:

score: 0
Accepted
time: 32ms
memory: 126656kb

input:

592 750
.......#..#.#......#.............#...............###..#..#.........#.#.......##.............#.#.#................#..#...#...#......#...#.............#..##..#.#..#..........#..##.#.#..#..#.#...#....#......####.........#..#......#...........#......#............#.###.......##.#..#.#.#...#.#.##....

output:

...............................................................................................................................................................................................................................................................................................................

result:

ok 592 lines

Test #4:

score: -100
Memory Limit Exceeded

input:

1768 1394
###.###.#######.###.#####.####.##########################.########.###################################.#########################################.#########################.####################.##############.###########################.#######################.################.####.#.#######...

output:


result: