2780827_ac_4665ms_8100k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {

	static int num;
	static int map[][] = new int [34*34][34*34];
	static int b[] = new int [34*34];
	static int link[] = new int [34*34];
	public static int dfs(int v)
	{
		int i;
		
		for (i = 1; i <= num; i++)
		{
			if (map[v][i]==1&&b[i]==0)
			{
				b[i] = 1;
				if (link[i]==0||dfs(link[i])==1)
				{
					link[i] = v;
					return 1;
				}
			}
		}
		return 0;
	}
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		int i, m, n, j, k, t;
		int x, y;
		int mark[][] = new int [34][34];
		int d[][] = new int [34][34];
		
		m = cin.nextInt();
		n = cin.nextInt();
		k = cin.nextInt();
		for (i = 0; i <= m; i++)
			for (j = 0; j <= n; j++)
				mark[i][j] = d[i][j] = 0;
		for (i = 0; i < k; i++)
		{
			x = cin.nextInt();
			y = cin.nextInt();
			mark[y][x] = 1;
		}
		num = 0;
		for (i = 1; i <= m; i++)
			for (j = 1; j <= n; j++)
				if (mark[i][j]==0)
				{
					num++;
					d[i][j] = num;
				}
		if (num%2!=0)
		{
			System.out.println("NO");
			return ;
		}
		for (i = 0; i <= num; i++)
			for (j = 0; j <= num; j++)
				map[i][j] = 0;
		for (i = 1; i <= m; i++)
			for (j = 1; j <= n; j++)
				if(mark[i][j]==0)
				{
					t = d[i][j];
					if (i-1>0&&mark[i-1][j]==0) map[t][d[i-1][j]]=1;
			        if (j-1>0&&mark[i][j-1]==0) map[t][d[i][j-1]]=1;
			        if (i+1<=m&&mark[i+1][j]==0) map[t][d[i+1][j]]=1;
			        if (j+1<=n&&mark[i][j+1]==0) map[t][d[i][j+1]]=1;
				}
		for (i = 1; i <= num; i++)
			link[i] = 0;
		for (i = 1; i <= num; i++)
		{
			for(j = 1; j <= num; j++)
				b[j] = 0;
			if(dfs(i)==0)
			{
				System.out.println("NO");
				return ;
			}
		}
		System.out.println("YES");
	}
}