pku2893.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define maxn 1000

int s[maxn][maxn], t[maxn][maxn];
int x[maxn * maxn], y[maxn * maxn], b[maxn * maxn];
int M, N;
int cnt;

void merge(int v[], int s, int mid, int e)
{
	int i, j, k;
	i = s;
	j = mid;
	k = s;
	while (i < mid && j < e)
	{
		if (v[i] < v[j])
		{
			b[k++] = v[i++];
		}
		else
		{
			b[k++] = v[j++];
			cnt += (mid - i);
			cnt = cnt & 1;
		}
	}
	while (i < mid)
		b[k++] = v[i++];
	while (j < e)
		b[k++] = v[j++];
	for (i = s; i < e; i++)
		v[i] = b[i];
}

void merge_sort(int v[], int s, int e)
{
	int mid;
	if (s + 1 == e)
		return;
	mid = (s + e) / 2;
	merge_sort(v, s, mid);
	merge_sort(v, mid, e);
	merge(v, s, mid, e);
}

void show(int v[])
{
	int i;
	for (i = 0; i < M * N; i++)
		printf("%d ", v[i]);
	printf("\n");
}

void Solve()
{
	int i, j, k;
	k = 1;
	cnt = 0;
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			t[i][j] = k++;
			scanf("%d", &s[i][j]);
			if (s[i][j] == 0)
			{
				cnt = (M + N - i - j - 2) & 1;
				s[i][j] = M * N;
			}
		}
	}
	k = 0;
	if (N % 2 == 0)
	{
		for (j = 0; j < N; j++)
		{
			for (i = 0; i < M; i++)
			{
				x[k] = s[i][j];
				y[k] = t[i][j];
				k++;
			}
		}
	}
	else
	{
		for (i = 0; i < M; i++)
		{
			for (j = 0; j < N; j++)
			{
				x[k] = s[i][j];
				y[k] = t[i][j];
				k++;
			}
		}
	}
	merge_sort(x, 0, M * N);
	merge_sort(y, 0, M * N);
	puts(cnt % 2? "NO":"YES");
}

int main()
{
	while (EOF != scanf("%d %d", &M, &N) && (M || N))
		Solve();
	return 0;
}