QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#68318 | #4788. Gravity | A_zjzj | TL | 25ms | 98248kb | C++14 | 1.1kb | 2022-12-15 18:46:14 | 2022-12-15 18:46:16 |
Judging History
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;
}
详细
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 #..###..##..#.####.##.##.###..#.....##..#.#.#.#......#.....##..#.##...#.#....#..##.###...#...##.###.#.....#.##.###...#..##.#...###..#.###.#...###..#.......#...#....#.#..#...##........#.#..#..##.....###...#..#.####..####...#..##......#........#..#.##.##..#..#....##.##.##..#..##.....###....#...