Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator