Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 附 ： 16MS代码。

Posted by yinqingwang at 2012-06-08 20:36:25 on Problem 2446
```思路：
(1) 化为2分图匹配。
(2) 格子分为奇偶, 奇和偶格子都编号，并且都是从1,2,3,顺序。（这样2分图的大小小很多）
(3) 格子坐标(i,j) -> 2分图的节点编号转换，并且事先计算好。
(4) 套算法了。

=====================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ROW (32*32/2 + 4)
#define MAX_COL (32*32/2 + 4)

int row,col;
int x_num,y_num,holes,x_holes;  //row: (0,32], colum:(0,32], and holes:[0,m*n]
int matrix[MAX_ROW][MAX_COL]; //
int id[MAX_ROW][MAX_COL]; //
int nid[MAX_ROW][4]; //neibor id
int match[MAX_COL], visit[MAX_COL];

int find_path(int v){ //here just only max 4 lines!
int i = 0,j=0;
for(j=0;j<4;j++){
i = nid[v][j];  //get neibor node!
if( matrix[v][i] && !visit[i] ){
visit[i] = 1; //

if( !match[i] ){
//ret = 1;
match[i] = v;
return 1;
}
else if(match[i]!=v) {
//ret = find_path(match[i]);
if( find_path(match[i]) ) {
match[i] = v;
return 1;
}
}
else{ //not need to find!
}
}
}
return 0;
}

void input()
{
#define get_num(m,n,i,j) (((i-1)*n + j + 1)/2)
#define is_x(i,j) ((i+j+1)%2)

int i,j;
int m,n,k;
scanf("%d %d %d",&m,&n,&k);
row = m;col=n;
x_num = (m*n+1)/2;
y_num = (m*n)/2;

holes = k;x_holes=0;

memset(match, 0 , sizeof(int)*(y_num+1)); //clear all match data!
memset(matrix, 0 , sizeof(int)*MAX_ROW*MAX_COL); //clear all data!
memset(id, 0 , sizeof(int)*MAX_ROW*MAX_COL); //clear all data!
memset(nid, 0 , sizeof(int)*MAX_ROW*4); //clear all data!

for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
id[i][j] = get_num(m,n,i,j);
}

for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
int x = id[i][j]; //get_num(m,n,i,j); //get no.

if( is_x(i,j) ){
if( i>1 ) {
matrix[x][id[i-1][j]] = 1;
nid[x][0]=id[i-1][j];
} //else{ nid[x][0]=0; }

if( i<m ) {
matrix[x][id[i+1][j]] = 1;
nid[x][1]=id[i+1][j];
} //else {nid[x][1] = 0;}

if( j>1 ) {
matrix[x][id[i][j-1]] = 1;
nid[x][2]=id[i][j-1];
} //else {nid[x][2] = 0;}

if( j<n ) {
matrix[x][id[i][j+1]] = 1;
nid[x][3]=id[i][j+1];
} //else { nid[x][3] = 0;}
}else{
//if( i>1 ) matrix[get_num(m,n,i-1,j)][x] = 1;
//if( i<m ) matrix[get_num(m,n,i+1,j)][x] = 1;
//if( j>1 ) matrix[get_num(m,n,i,j-1)][x] = 1;
//if( j<n ) matrix[get_num(m,n,i,j+1)][x] = 1;

}
}
}
while(k --){
scanf("%d %d",&j,&i);
int x = get_num(m,n,i,j); //get no.
if( is_x(i,j) ){
x_holes ++;
if( i>1 ) matrix[x][get_num(m,n,i-1,j)] = 0;
if( i<m ) matrix[x][get_num(m,n,i+1,j)] = 0;
if( j>1 ) matrix[x][get_num(m,n,i,j-1)] = 0;
if( j<n ) matrix[x][get_num(m,n,i,j+1)] = 0;
}else{
if( i>1 ) matrix[get_num(m,n,i-1,j)][x] = 0;
if( i<m ) matrix[get_num(m,n,i+1,j)][x] = 0;
if( j>1 ) matrix[get_num(m,n,i,j-1)][x] = 0;
if( j<n ) matrix[get_num(m,n,i,j+1)][x] = 0;

}
}

}

void solve()
{
int ans = 0, i=0;

input(); // input data!

if( (x_num - x_holes) != (y_num - holes + x_holes) ){
puts("NO");
}else{

for(i=1;i<=x_num;i++){
memset(visit, 0, sizeof(int)*(y_num+1));
if( find_path(i) ) ans ++;
}
if( ans + x_holes == x_num ) puts("YES");
else puts("NO");

}
//printf("x_num=%d, y_num=%d, x_holes=%d,y_holes=%d ,ans=%d\n",x_num,y_num,x_holes,holes-x_holes,ans);

}

int main()
{
//printf("Hello \n");
solve();
return 0;
}
```

Followed by: