QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213019 | #1978. Stabbing Number | ucup-team1004 | AC ✓ | 54ms | 3896kb | C++14 | 2.6kb | 2023-10-14 07:32:36 | 2023-10-14 07:32:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=105,INF=1e9;
int n,m,k,h[N],c[N],cur[N];
char str[N][N],a[N][N],b[N][N];
bool in[N][N];
void ins(int i){
int l=c[i],r=l,x=h[i]-1,y=x;
for(;l>1&&b[x][l-1]=='.';l--);
for(;r<m&&b[x][r+1]=='.';r++);
for(;y>1&&b[y-1][l]=='.';y--);
for(int i=l-1;i<=r+1;i++)b[x+1][i]=b[y-1][i]='*';
for(int i=y-1;i<=x+1;i++)b[i][l-1]=b[i][r+1]='*';
// for(int i=n;i>=1;i--)debug(b[i]+1);
// debug('\n');
}
int calc(){
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='*'||in[i][j-1])continue;
int cnt=0;
for(int k=j;k<=m&&in[i][k];k++){
cnt+=b[i][k]=='*'&&b[i][k-1]!='*'&&b[i][k+1]!='*';
}
// if(cnt==3)debug("right",i,j);
ans=max(ans,cnt);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='*'||in[i+1][j])continue;
int cnt=0;
for(int k=i;k>=1&&in[k][j];k--){
cnt+=b[k][j]=='*'&&b[k-1][j]!='*'&&b[k+1][j]!='*';
}
// if(cnt==3)debug("down",i,j);
ans=max(ans,cnt);
}
}
// for(int i=n;i>=1;i--)debug(b[i]+1);
// debug('\n');
return ans-1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=n;i>=1;i--)scanf("%s",str[i]+1);
for(int i=1;i<=n*2-1;i++){
for(int j=1;j<=m;j++)a[i][j]='.';
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str[i][j]=='*'&&str[i+1][j]=='*'){
a[i*2-1][j]=a[i*2][j]=a[i*2+1][j]='*';
}
if(str[i][j]=='*'&&str[i][j+1]=='*'){
a[i*2-1][j]=a[i*2-1][j+1]='*';
}
}
}
n=n*2-1,m=m*2-1;
for(int j=1;j<=m;j++){
int mx=0,mn=n+1;
for(int i=1;i<=n;i++){
if(a[i][j]=='*')mx=max(mx,i),mn=min(mn,i);
}
for(int i=mn;i<=mx;i++){
in[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int l=1,r;l<=m;l=r){
for(r=l;r<=m&&a[i][r]==a[i][l];r++);
if(a[i][l]=='*'&&l+1<r&&in[i-1][l])h[++k]=i,c[k]=l+1;
}
}
// debug(ary(h,1,k),ary(c,1,k));
iota(cur,cur+1+k,0);
int ans=INF;
// cur[1]=3,cur[2]=1,cur[3]=2,cur[4]=5,cur[5]=4;
do{
memcpy(b,a,sizeof a);
for(int i=1;i<=k;i++)ins(cur[i]);
ans=min(ans,calc());
}while(next_permutation(cur+1,cur+1+k));
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
input:
10 13 .....****.... .....*..*.... .....*..***.. .....*....*.. .....*....*** ...***......* ...*........* ****........* *...........* *************
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
8 15 ............... .........*****. ....***..*...*. ....*.*..*...*. .****.****...*. .*...........*. .*************. ...............
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 16ms
memory: 3784kb
input:
16 25 ...............********** ...............*........* ............****........* ............*...........* ..........***...........* ..........*.............* ........***.............* ........*...............* .....****...............* .....*..................* .....*..................* ...***.....
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 13ms
memory: 3896kb
input:
13 25 ........******........... ........*....*........... .....****....*........... .....*.......****........ .....*..........*........ .....*..........****..... .....*.............*..... .....*.............****** ...***..................* ...*....................* ****....................* *..........
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 13ms
memory: 3884kb
input:
13 25 ........******........... ........*....*........... .....****....****........ .....*..........*........ .....*..........*........ .....*..........*........ .....*..........*........ .....*..........*........ ...***..........*****.... ...*................*.... ****................***** *..........
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 9ms
memory: 3848kb
input:
8 24 .........****....******* ...****..*..*....*.....* ...*..*..*..*..***.....* ****..*..*..*..*.......* *.....****..*..*.......* *...........****.......* *......................* ************************
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 10ms
memory: 3824kb
input:
10 24 ...............****..... .........****..*..*..... ...****..*..*..*..*..... ...*..*..*..*..*..*..... ****..*..*..*..*..*..... *.....****..*..*..*..... *...........****..*..... *.................****** *......................* ************************
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 13ms
memory: 3824kb
input:
14 25 ........******........... ........*....*........... .....****....*........... .....*.......*........... .....*.......*****....... .....*...........*....... ...***...........*....... ...*.............*....... ...*.............****.... ...*................*.... ****................*.... *..........
output:
3
result:
ok single line: '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
20 20 .................... .................... .................... .................... .................... .................... .................... .................... .................... .**************..... .*............*..... .*............*..... .*............*..... .**************..... ...
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
20 20 .................... .................... .................... .................... ......*********..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......*..... ......*.......****** ...
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
20 20 .................... .................... .................... ......****.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ......*..*.......... ...
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
20 20 .................... .................... .................... .****............... .*..*............... .*..*.......*****... .*..*.......*...*... .*..*****...*...*... .*......*...*...*... .*......*...*...*... .*......*...*...*... .*......*...*...*... .*......*...*...*... .*......*...*...*... ...
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
40 40 ........................................ ..............******.................... ..............*....*.................... ..............*....*.................... ..............*....*.................... ..............*....*.................... ..............*....*.................... ..........
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
40 40 ..........*****......................... ..........*...*......................... ..........*...*......................... ..........*...*......................... ......*****...*......................... ......*.......*......................... ......*.......*.........******.......... ......*...
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 51ms
memory: 3896kb
input:
40 40 .................*****.................. .................*...*.......***........ .................*...*.......*.*........ .................*...*.......*.*........ .................*...*.......*.*........ .................*...*.......*.*........ .................*...*.......*.*........ ..........
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 49ms
memory: 3856kb
input:
40 40 ...............******................... ...............*....*................... ...............*....*................... ...............*....*................... ...............*....*................... ...............*....*................... ...............*....*................... ..........
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 49ms
memory: 3772kb
input:
40 40 .....................****............... .....................*..*.***........... .............***.....*..*.*.*........... .............*.*.....*..*.*.*........... .............*.*.....*..*.*.*........... .............*.*.***.*..*.*.*........... .............*.*.*.*.*..*.*.*........... ..........
output:
3
result:
ok single line: '3'
Test #18:
score: 0
Accepted
time: 54ms
memory: 3892kb
input:
40 40 ........................................ ........................................ ........................................ ........................................ ........................................ ........................................ ........................................ ..........
output:
3
result:
ok single line: '3'