QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213018#1978. Stabbing Numberucup-team1004WA 6ms3828kbC++142.2kb2023-10-14 07:25:242023-10-14 07:25:24

Judging History

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

  • [2023-10-14 07:25:24]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3828kb
  • [2023-10-14 07:25:24]
  • 提交

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=55,INF=1e9;
int n,m,k,h[N],c[N],cur[N];
char 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);
	return ans-1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=n;i>=1;i--)scanf("%s",a[i]+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: 3828kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

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

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 5ms
memory: 3732kb

input:

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

output:

3

result:

ok single line: '3'

Test #6:

score: -100
Wrong Answer
time: 4ms
memory: 3756kb

input:

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

output:

3

result:

wrong answer 1st lines differ - expected: '2', found: '3'