QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#516164#6398. Puzzle: TapahuayucaijiRE 0ms0kbC++142.8kb2024-08-12 14:05:072024-08-12 14:05:07

Judging History

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

  • [2024-08-12 14:05:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-08-12 14:05:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int MAXN=2.5e3+10;

int n,m,stp,cnt;
int a[110][110],h[MAXN],vis[MAXN],match[MAXN],b[110][110];
char mp[110][110];

char read_char() {
  char ch=getchar();
  while(!isdigit(ch)&&ch!='.') {
    ch=getchar();
  }
  return ch;
}

int idx(int i,int j) {
  return (i-1)*((m+1)/2)+j;
}
void repair(int &x,int &y,int idx) {
  x=(idx-1)/((m+1)/2)+1;
  y=(idx-1)%((m+1)/2)+1;
}

struct edge {
  int v,nxt;
}e[MAXN<<3];

void addedge(int u,int v) {
  e[++cnt].v=v;
  e[cnt].nxt=h[u];
  h[u]=cnt;
}
void insert(int u,int v) {
  addedge(u,v);
  addedge(v,u);
}

bool dfs(int u) {
  for(int i=h[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(vis[v]!=stp) {
      vis[v]=stp;
      if(match[v]==-1||dfs(match[v])) {
        match[v]=u;
        //match[u]=v;
        return 1;
      }
    }
  }
  return 0;
}

int main() {
  cin>>n>>m;
  n=2*n-1;
  m=2*m-1;
  int k=0;
  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
      mp[i][j]=read_char();
      if((i&1)&&(j&1)) {
        int x=a[(i+1)/2][(j+1)/2]=mp[i][j]-'0';
        if(x==2||x==4||x==7) {
          k++;
          b[(i+1)/2][(j+1)/2]=1;
        }
      }
      else {
        mp[i][j]='#';
      }
    }
  }

  for(int i=1;i<=(n+1)/2;i++) {
    for(int j=1;j<=(m+1)/2;j++) {
      int x,y;
      x=i+1,y=j;
      if(x<=(n+1)/2&&y<=(m+1)/2) {
        if(i+x-1==2||i+x-1==n-1) {
          if(j>1&&j<(m+1)/2) continue;
        }
        if(b[i][j]&&b[x][y]) {
          insert(idx(i,j),idx(x,y));
        }
      }
    }
    for(int j=1;j<=(m+1)/2;j++) {
      int x=i,y=j+1;
      if(x<=(n+1)/2&&y<=(m+1)/2) {
        if(y+j-1==2||y+j-1==m-1) {
          if(i>1&&i<(n+1)/2) continue;
        }
        if(b[i][j]&&b[x][y]) {
          insert(idx(i,j),idx(x,y));
        }
      }
    }
  }

  fill(match+1,match+idx((n+1)/2,(m+1)/2)+1,-1);
  for(int i=1;i<=idx((n+1)/2,(m+1)/2);i++) {
    stp++; 
    k-=dfs(i);
  }
  if(k!=0) {
    puts("NO");
    return 0;
  }

  for(int i=1;i<=idx((n+1)/2,(m+1)/2);i++) {
    int x,y;
    repair(x,y,i);
  
    if(!b[x][y]) {
      continue;
    }
    if(match[i]==-1) {
      continue;
    }
    if(match[match[i]]==i) {
      assert(0);
    }
    int a,b;
    repair(a,b,match[i]);
    x=2*x-1;
    y=2*y-1;
    a=2*a-1;
    b=2*b-1;

    mp[(x+a)/2][(y+b)/2]='.';
  }

  puts("YES");
  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
      putchar(mp[i][j]);
    }
    puts("");
  }
  return 0;
}
/*
2 5
2.4.4.4.3
.........
3.4.4.4.2

3 2
3.3
...
4.4
...
3.3

2 2
2.3
...
3.2

5 5
3.5.5.5.3
.........
5.7.7.7.5
.........
5.7.7.7.5
.........
5.8.8.8.4
.........
3.5.5.5.2

3 3
2.4.2
.....
4.8.4
.....
2.4.2

2 2
2.2
...
2.2
*/

详细

Test #1:

score: 0
Runtime Error

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:


result: