文章目录

潘少的 BLOG

诗酒趁年华

X

ACM刷题之-POJ-1021(2D-Nim)

  panjf2000

Description

The 2D-Nim board game is played on a grid, with pieces on the grid points. On each move, a player may remove any positive number of contiguous pieces in any row or column. The player who removes the last piece wins. For example, consider the left grid in the following figure.
image
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-playing software, a certain programmer wants to be able to tell whether or not a certain 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. That is, if there is a winning strategy for the left board, the same one must apply to the right board. The fact that the contiguous groups of pieces appear in different places and orientations is clearly irrelevant. All that matters is that the same clusters of pieces (a cluster being a set of contiguous pieces that can be reached from each other by a sequence of one-square vertical or horizontal 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 left and right), rotated, and moved. Your task is to determine whether two given board states are equivalent in this sense or not.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. 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 grid in terms of the number of grid points. n is the number of pieces on each board. The second line of each test case contains a sequence of n pairs of integers xi , yi, giving the 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 pieces on the second board in the same format.

Output

Your program should produce a single line for each test case containing a word YES or NO indicating whether the two boards are equivalent or not.

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

Sample Output

YES NO

我的答案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct position{
      int x,y;      
}pos[10010];

int w,h,n,map[105][105],sum[2][10010];

int main(){
   int T;
   cin>>T;
   while (T--){
       cin >> w >> h >> n;
       memset(map,0,sizeof map);
       for (int i = 1;i <= n;i ++) {
           cin >> pos[i].x >> pos[i].y;
           map[pos[i].x][pos[i].y] = 1;
       }
       for (int i = 1;i <= n;i ++){
           int xx = pos[i].x,yy = pos[i].y,x,y,cnt = 0;
           for (x = xx,y = yy;map[x][y] && y < h;++y,++cnt);
           for (x = xx,y = yy;map[x][y] && x < w;++x,++cnt);
           for (x = xx,y = yy;map[x][y] && y >= 0;--y,++cnt);
           for (x = xx,y = yy;map[x][y] && x >= 0;--x,++cnt);
           sum[0][i] = cnt;
       }
       
       memset(map,0,sizeof map);
       for (int i = 1;i <= n;i ++) {
           cin >> pos[i].x >> pos[i].y;
           map[pos[i].x][pos[i].y] = 1;
       }
       
       for (int i = 1;i <= n;i ++){
           int xx = pos[i].x,yy = pos[i].y,x,y,cnt = 0;
           for (x = xx,y = yy;map[x][y] && y < h;++y,++cnt);
           for (x = xx,y = yy;map[x][y] && x < w;++x,++cnt);
           for (x = xx,y = yy;map[x][y] && y >= 0;--y,++cnt);
           for (x = xx,y = yy;map[x][y] && x >= 0;--x,++cnt);
           sum[1][i] = cnt;
       }
       
       sort(sum[0] + 1,sum[0] + 1 + n);
       sort(sum[1] + 1,sum[1] + 1 + n);
       
       int pd = 1;
       for (int i = 1;i <= n;i ++) if (sum[0][i] != sum[1][i]) {
           pd = 0;break;
       }
       
       if (!pd) puts("NO");
       else puts("YES");
   }
   
   return 0;
}


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:ACM刷题之-POJ-1021(2D-Nim)
作者:潘建锋
原文:https://taohuawu.club/POJ-1021

关于留言和评论

如果您对本文《ACM刷题之-POJ-1021(2D-Nim)》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~