QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68317 | #4788. Gravity | A_zjzj | WA | 15ms | 98456kb | C++14 | 1.1kb | 2022-12-15 18:45:54 | 2022-12-15 18:45:55 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 98456kb
input:
10 10 .......... ..######.. ..#....#.. ..#.#..#.. ..#..#.#.. ..#....#.. ..######.. .......... ..#....#.. .......#..
output:
0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 8 8 8 0 0 0 0 7 0 0 0 0 7 0 0 0 0 6 0 4 0 0 6 0 0 0 0 5 0 0 4 0 5 0 0 0 0 4 0 0 0 0 4 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 .......... .......... ..######.. ..#....#.. ..#....#.. ..#....#.. ..#.##.#.. ..######.. .....
result:
wrong answer 1st lines differ - expected: '..........', found: '0 0 0 0 0 0 0 0 0 0 '