#P10755. 世界大战

世界大战

题目描述

两人在一个 n×mn\times m 的棋盘上进行游戏。每格的士兵属于同盟国或轴心国,分别用 00、11 表示。Nick 先手,随后两人交替操作。

一次操作选取一个矩形 (x1,y1)(x_1,y_1) 到 (x2,y2)(x_2,y_2),其中 1≤x1≤x2≤n1\le x_1\le x_2\le n,1≤y1≤y2≤m1\le y_1\le y_2\le m。必须保证右下角 (x2,y2)(x_2,y_2) 当前是 11。将上边界和下边界上所有格子的阵营反转,即 00 与 11 互换。若 x1=x2x_1=x_2,同一排只反转一次。

棋盘上没有 11 时,轮到操作的玩家输。双方都采取最优策略,判断谁获胜。

输入格式

第一行一个正整数 TT。每组先输入两个整数 n,mn,m,接下来 nn 行,每行一个长度为 mm 的二进制串。

输出格式

每组输出一行。若 Nick 获胜,输出 N,否则输出 C。

样例 1

2
2 2
01
10
3 3
111
101
111
C
N

样例 2

2
1 3
111
3 1
1
1
1
N
C

数据范围

  • 20%20\% 的数据满足 n,m≤3n,m\le3。
  • 15%15\% 的数据满足 n=1n=1。
  • 另外 15%15\% 的数据满足 m=1m=1。
  • 所有数据满足 1≤n,m≤3001\le n,m\le300,1≤T≤301\le T\le30。

原 PDF 题面