[UVA][基於概率] 10707 - 2D-Nim
Problem C
2-D Nim
Input: standard input
Output: standard output
TimeLimit: 1 second
The 2D-Nim board game is played on a grid, withpieces on the grid points. On each move, a player may remove any positive numberof contiguous pieces in any row or column. The player who removes the lastpiece wins. For example, consider the left grid in the following figure.
The player on move may remove (A), (B), (A,B), (A, B, C), or (B,F), etc., but may not remove (A, C),(D, E), (H, I) or (B, G). For purposes of writing 2D-Nim-playingsoftware, a certain programmer wants to be able to tell whether or not acertain position has ever been analyzed previously. Because of the rules of 2D-Nim,it should be clear that the two boards above are essentially equivalent. Thatis, if there is a winning strategy for the left board, the same one must applyto the right board. The fact that the contiguous groups of pieces appear indifferent places and orientations is clearly irrelevant. All that matters isthat the same clusters of pieces (a cluster being a set of contiguous piecesthat can be reached from each other by a sequence of one-square vertical orhorizontal moves) appear in each. For example, the cluster of pieces (A, B,C, F, G) appears on both boards, but it has been reflected (swapping leftand right), rotated, and moved. Your task is to determine whether two givenboard states are equivalent in this sense or not.
Input
The first line of the input file contains a single integert (1<=t<=12), the number of test cases, followed by the input data for each testcase. The first line of each test case consists of three integers W, H,and n (1 <=W, H<=100). W is the width, and H is the height of the gridin terms of the number of grid points. n(n<=3000) is the number of pieces on each board. Thesecond line of each test case contains a sequence of npairs of integers xi,yi, givingthe coordinates of the pieces on the first board (0 =< xi < W and 0 =< yi<H). The third line of the test case describes the coordinates of the pieceson the second board in the same format.
Output
Your program should produce a single line for each testcase containing a word YES or NO indicating whether the twoboards are equivalent or not.
SampleInput Output for Sample Input
2 8 5 11 0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 5 2 4 4 0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4 8 5 11 0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 6 1 4 4 0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
| YES NO
|
Problem Source: IranianContest
Special Thanks: Jimmy Mårdell, EPS.
唯一的难点是，怎么判断连成一片的棋子形状相同？ 一个基于概率的算法是：给每一颗棋子计算一个值，根据这个值是否相等来推测它所在的一片棋子的形状是否相等。计算出每颗棋子的值后对其进行排序，若两副棋盘生成的序列完全相等则推测其等价。
至于这个值如何定，我的设计为：每颗棋子在其水平方向和垂直方向与其相连的棋子总数+1（自己）。比如左图的C，这个值为水平相连2颗(AB)+垂直相连1颗(G)+1=4。
很少做這種題目，覺得挺有趣的！
忘了講解題目意思，原本以為要問 2D-NIM 的誰輸誰贏，結果是要求算兩者的盤面等不等價。
#include <stdio.h>
#include <algorithm>
using namespace std;
void calcAdj(int w, int h, int g[][105], int ans[]) {
int i, j, k, cnt;
static int L[105][105], R[105][105], U[105][105], D[105][105];
for(i = 0; i < w; i++)
for(j = 0, cnt = 0; j < h; j++)
cnt = g[i][j] ? cnt+g[i][j]:0, L[i][j] = cnt;
for(i = 0; i < w; i++)
for(j = h-1, cnt = 0; j >= 0; j--)
cnt = g[i][j] ? cnt+g[i][j]:0, R[i][j] = cnt;
for(j = 0; j < h; j++)
for(i = 0, cnt = 0; i < w; i++)
cnt = g[i][j] ? cnt+g[i][j]:0, U[i][j] = cnt;
for(j = 0; j < h; j++)
for(i = w-1, cnt = 0; i >= 0; i--)
cnt = g[i][j] ? cnt+g[i][j]:0, D[i][j] = cnt;
k = 0;
for(i = 0; i < w; i++) {
for(j = 0; j < h; j++) {
if(g[i][j])
ans[k++] = L[i][j]+R[i][j]+U[i][j]+D[i][j];
}
}
sort(ans, ans+k);
}
int main() {
int testcase;
int W, H, n, i, x, y;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &W, &H, &n);
int g1[105][105] = {}, g2[105][105] = {};
int adj1[3005], adj2[3005];
for(i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
g1[x][y] = 1;
}
for(i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
g2[x][y] = 1;
}
calcAdj(W, H, g1, adj1);
calcAdj(W, H, g2, adj2);
for(i = 0; i < n; i++) {
if(adj1[i] != adj2[i])
break;
}
if(i == n)
puts("YES");
else
puts("NO");
}
return 0;
}