本人检查很久没发现问题,结果 WA 5pts,仅 #1 AC。
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int tot_node = 1609;
vector<int>e[tot_node];//边
int mat[tot_node];//匹配节点
bool vis[tot_node];//不撞环
int del;//试图删掉
bool H_srh(int v){//匈牙利算法的搜索
for(int i = 0; i < e[v].size(); i ++){
if(vis[e[v][i]] || e[v][i] == del)
continue;
vis[e[v][i]] = true;
if(mat[e[v][i]] == 0 || H_srh(mat[e[v][i]])){//可以匹配
mat[e[v][i]] = v,mat[v] = e[v][i];//匹配
vis[e[v][i]] = false;
return true;
}
}
return false;
}
int n,m,c[49][49],x,y,k;
//这个网格将白格和其它构成二分图
int blk(int _x,int _y){//格子对应的点
return (_x - 1) * m + _y;
}
vector<int>f;
bool lf,nf;
void f0(){
if(mat[blk(x,y)] == 0){
nf = false;
}
else{
del = blk(x,y);
mat[mat[blk(x,y)]] = 0;
memset(vis,false,sizeof(bool) * (n * m + 1));
if(H_srh(mat[blk(x,y)])){
nf = false;
mat[blk(x,y)] = 0;//去匹配
}
else{
nf = true;
mat[mat[blk(x,y)]] = blk(x,y);
}
}
}
void f1(){
if(mat[blk(x,y)] == 0){
lf = false;
}
else{
del = blk(x,y);
mat[mat[blk(x,y)]] = 0;
memset(vis,false,sizeof(bool) * (n * m + 1));
if(H_srh(mat[blk(x,y)])){
lf = false;
mat[blk(x,y)] = 0;//去匹配
}
else{
lf = true;
mat[mat[blk(x,y)]] = blk(x,y);
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
scanf(" %c",&c[i][j]);
if(c[i][j] == 'O'){
if(i > 1 && c[i - 1][j] != 'O'){//向上建边
e[blk(i,j)].push_back(blk(i - 1,j));
e[blk(i - 1,j)].push_back(blk(i,j));
}
if(j > 1 && c[i][j - 1] != 'O'){//向左建边
e[blk(i,j)].push_back(blk(i,j - 1));
e[blk(i,j - 1)].push_back(blk(i,j));
}
}
else{
if(c[i][j] == '.'){
x = i,y = j;
}
if(i > 1 && c[i - 1][j] == 'O'){//向上建边
e[blk(i,j)].push_back(blk(i - 1,j));
e[blk(i - 1,j)].push_back(blk(i,j));
}
if(j > 1 && c[i][j - 1] == 'O'){//向左建边
e[blk(i,j)].push_back(blk(i,j - 1));
e[blk(i,j - 1)].push_back(blk(i,j));
}
}
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){//匈牙利匹配,经测试只能找一个集合
if(c[i][j] == 'O' || mat[blk(i,j)] == 0)
continue;
memset(vis,false,sizeof(bool) * (n * m + 1));
H_srh(blk(i,j));
}
}
scanf("%d",&k);
if(mat[blk(x,y)] == 0){
lf = false;
}
else{
del = blk(x,y);
mat[mat[blk(x,y)]] = 0;
memset(vis,false,sizeof(bool) * (n * m + 1));
if(H_srh(mat[blk(x,y)])){
lf = false;
mat[blk(x,y)] = 0;//去匹配
}
else{
lf = true;
mat[mat[blk(x,y)]] = blk(x,y);
}
}
for(int i = 1; i <= 2 * k; i ++){
scanf("%d %d",&x,&y);
if((i & 1) == 0)
f1();
else{
f0();
if(lf && nf){
f.push_back((i + 1) >> 1);
}
}
}
printf("%u\n",f.size());
for(unsigned i = 0; i < f.size(); i ++){
printf("%d\n",f[i]);
}
return 0;
}