QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68318#4788. GravityA_zjzjTL 25ms98248kbC++141.1kb2022-12-15 18:46:142022-12-15 18:46:16

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 18:46:16]
  • 评测
  • 测评结果:TL
  • 用时:25ms
  • 内存:98248kb
  • [2022-12-15 18:46:14]
  • 提交

answer

#include<bits/stdc++.h>
#define id(x,y) ((x-1)*m+y)
using namespace std;using ll=long long;const int N=2e3+10,M=N*N;
int n,m,k,d[N][N],f[M];char a[N][N],b[N][N];vector<pair<int,int> >A[M];
void add(int u,int v,int w){A[u].push_back({v,w});}
void bfs(){
	queue<int>q;for(int j=1;j<=m;j++)q.push(id(n+1,j));for(int u;!q.empty();q.pop()){
		u=q.front();for(auto [v,w]:A[u])if(f[v]<f[u]+w)f[v]=f[u]+w,q.push(v);
	}
}
int main(){
	scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);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]=='#')add(id(d[i+1][j],j),id(i,j),1);
	for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[i][j]=='#'&&a[i][j+1]=='#'){
		add(id(i,j),id(i,j+1),0),add(id(i,j+1),id(i,j),0);
	}bfs();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[f[id(i,j)]][j]='#';
	for(int i=n;i>=1;i--)printf("%s\n",b[i]+1);return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 25ms
memory: 98248kb

input:

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


output:

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

result:

ok 10 lines

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:


result: