QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213020#1978. Stabbing Numberucup-team1004AC ✓39ms3776kbC++142.6kb2023-10-14 07:34:422023-10-14 07:34:42

Judging History

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

  • [2023-10-14 07:34:42]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:3776kb
  • [2023-10-14 07:34:42]
  • 提交

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;
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3520kb

input:

10 13
.....****....
.....*..*....
.....*..***..
.....*....*..
.....*....***
...***......*
...*........*
****........*
*...........*
*************

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

8 15
...............
.........*****.
....***..*...*.
....*.*..*...*.
.****.****...*.
.*...........*.
.*************.
...............

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 9ms
memory: 3524kb

input:

16 25
...............**********
...............*........*
............****........*
............*...........*
..........***...........*
..........*.............*
........***.............*
........*...............*
.....****...............*
.....*..................*
.....*..................*
...***.....

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 8ms
memory: 3764kb

input:

13 25
........******...........
........*....*...........
.....****....*...........
.....*.......****........
.....*..........*........
.....*..........****.....
.....*.............*.....
.....*.............******
...***..................*
...*....................*
****....................*
*..........

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 8ms
memory: 3552kb

input:

13 25
........******...........
........*....*...........
.....****....****........
.....*..........*........
.....*..........*........
.....*..........*........
.....*..........*........
.....*..........*........
...***..........*****....
...*................*....
****................*****
*..........

output:

3

result:

ok single line: '3'

Test #6:

score: 0
Accepted
time: 6ms
memory: 3648kb

input:

8 24
.........****....*******
...****..*..*....*.....*
...*..*..*..*..***.....*
****..*..*..*..*.......*
*.....****..*..*.......*
*...........****.......*
*......................*
************************

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3664kb

input:

10 24
...............****.....
.........****..*..*.....
...****..*..*..*..*.....
...*..*..*..*..*..*.....
****..*..*..*..*..*.....
*.....****..*..*..*.....
*...........****..*.....
*.................******
*......................*
************************

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 4ms
memory: 3656kb

input:

14 25
........******...........
........*....*...........
.....****....*...........
.....*.......*...........
.....*.......*****.......
.....*...........*.......
...***...........*.......
...*.............*.......
...*.............****....
...*................*....
****................*....
*..........

output:

3

result:

ok single line: '3'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
.**************.....
.*............*.....
.*............*.....
.*............*.....
.**************.....
...

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

20 20
....................
....................
....................
....................
......*********.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......*.....
......*.......******
...

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

20 20
....................
....................
....................
......****..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
......*..*..........
...

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

20 20
....................
....................
....................
.****...............
.*..*...............
.*..*.......*****...
.*..*.......*...*...
.*..*****...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
.*......*...*...*...
...

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

40 40
........................................
..............******....................
..............*....*....................
..............*....*....................
..............*....*....................
..............*....*....................
..............*....*....................
..........

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 4ms
memory: 3536kb

input:

40 40
..........*****.........................
..........*...*.........................
..........*...*.........................
..........*...*.........................
......*****...*.........................
......*.......*.........................
......*.......*.........******..........
......*...

output:

2

result:

ok single line: '2'

Test #15:

score: 0
Accepted
time: 26ms
memory: 3556kb

input:

40 40
.................*****..................
.................*...*.......***........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
.................*...*.......*.*........
..........

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 25ms
memory: 3664kb

input:

40 40
...............******...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
...............*....*...................
..........

output:

2

result:

ok single line: '2'

Test #17:

score: 0
Accepted
time: 24ms
memory: 3560kb

input:

40 40
.....................****...............
.....................*..*.***...........
.............***.....*..*.*.*...........
.............*.*.....*..*.*.*...........
.............*.*.....*..*.*.*...........
.............*.*.***.*..*.*.*...........
.............*.*.*.*.*..*.*.*...........
..........

output:

3

result:

ok single line: '3'

Test #18:

score: 0
Accepted
time: 39ms
memory: 3556kb

input:

40 40
........................................
........................................
........................................
........................................
........................................
........................................
........................................
..........

output:

3

result:

ok single line: '3'