QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297632 | #2563. Curly Racetrack | linweitong | WA | 1ms | 5628kb | C++14 | 2.3kb | 2024-01-04 21:10:43 | 2024-01-04 21:10:44 |
Judging History
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'