QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297632#2563. Curly RacetracklinweitongWA 1ms5628kbC++142.3kb2024-01-04 21:10:432024-01-04 21:10:44

Judging History

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

  • [2024-01-04 21:10:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5628kb
  • [2024-01-04 21:10:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,cnt,cnt0,ti,anss,s;
char a[N][N];
struct Lim{
	int x,l,r,tp;
}b[N*N*2];
vector<int>v[N*N*2];
int match[N*N*2],vis[N*N*2];
bool dfs(int x){
	if (vis[x]==ti)return 0;
	vis[x]=ti;
	for (int y:v[x]){
		if ((!match[y])||dfs(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){	
	scanf("%d%d",&n,&m);s=n*m;
	for (int i=1;i<=n;++i)scanf("%s",a[i]+1);
	for (int i=1;i<=n;++i){
		a[i][0]='1',a[i][m+1]='3';
		int las=-1;
		for (int j=0;j<=m+1;++j){
			if (a[i][j]=='x')las=-1,--s;
			if (a[i][j]>='1'&&a[i][j]<='4'){
				if (las>=0){
					int x=(a[i][las]-'1')/2,y=(a[i][j]-'1')/2;
					if (x==0&&y==0){
						if ((j-las)&1)b[++cnt]=(Lim){i,las+1,j-1,0}; 
					}
					if (x==0&&y==1){
						if ((j-las)%2==0)b[++cnt]=(Lim){i,las+1,j-1,0}; 
					}
					if (x==1&&y==0){
						if ((j-las)%2==0)b[++cnt]=(Lim){i,las+1,j-1,0};
					}
					if (x==1&&y==1){
						if ((j-las)&1)b[++cnt]=(Lim){i,las+1,j-1,0};
					}
				}
				las=j;
			}
		}
	}
	cnt0=cnt;
	for (int j=1;j<=m;++j){
		a[0][j]='1',a[n+1][j]='2';
		int las=-1;
		for (int i=0;i<=n+1;++i){
			if (a[i][j]=='x')las=-1;
			if (a[i][j]>='1'&&a[i][j]<='4'){
				if (las>=0){
					int x=(a[i][j]-'1')%2,y=(a[las][j]-'1')%2;
					if (x==0&&y==0){
						if ((i-las)&1)b[++cnt]=(Lim){j,las+1,i-1,1};
					} 
					if (x==0&&y==1){
						if ((i-las)%2==0)b[++cnt]=(Lim){j,las+1,i-1,1};
					} 
					if (x==1&&y==0){
						if ((i-las)%2==0)b[++cnt]=(Lim){j,las+1,i-1,1};
					} 
					if (x==1&&y==1){
						if ((i-las)&1)b[++cnt]=(Lim){j,las+1,i-1,1};
					} 
				}
				las=i;
			}
		}
	}
	for (int i=1;i<=cnt;++i){
		if (b[i].l>b[i].r)return !printf("-1");
		if (!b[i].tp){
			int ck=0;
			for (int j=b[i].l;j<=b[i].r;++j)if (a[b[i].x][j]=='o')++ck;
			if (ck==b[i].r-b[i].l+1)return !printf("-1");
		}else{
			int ck=0;
			for (int j=b[i].l;j<=b[i].r;++j)if (a[j][b[i].x]=='o')++ck;
			if (ck==b[i].r-b[i].l+1)return !printf("-1");
		}
	}
	for (int i=1;i<=cnt0;++i)
		for (int j=cnt0+1;j<=cnt;++j)
			if (b[j].x>=b[i].l&&b[j].x<=b[i].r&&b[i].x>=b[j].l&&b[i].x<=b[j].r)
				v[i].push_back(j);
	for (int i=1;i<=cnt0;++i){
		++ti;
		if (dfs(i))++anss;
	}
	anss=cnt-anss;
	printf("%d\n",s-anss);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5628kb

input:

4 5
4...x
.2..2
.o1x.
3..3o

output:

13

result:

wrong answer 1st numbers differ - expected: '12', found: '13'