카드 뒤집기 게임은 혼자서 하는 카드 게임으로, 두 가지 타입의 카드 A, B를 사용한다. 카드 A에는 게임에 적용될 규칙에 관한 정보가 적혀 있다. 구체적으로, 그림 1과 같이 두 정수 $N$과 $M(\le N)$, 그리고 $N \times N$ 격자 형태로 문자 ‘O’와 ‘X’가 배치된 패턴 $P$가 적혀 있다.
그림 1
카드 B는 앞면에 문자 ‘O’, 뒷면에 문자 ‘X’가 적힌 카드다. 카드 B 한 장은 카드 A에 적힌 패턴의 문자 하나를 나타내기 위해 사용될 것인데, 이를 위해 충분히 많은 양의 카드 B가 준비되어 있다.
게임을 시작해보자. 먼저, 카드 A를 하나 선택하고, 그 카드에 적힌 $N$ 값에 따라 $N \times N$ 격자 형태로 카드 B를 배치한다. 처음 배치되는 카드는 모두 ‘X’가 보이도록 배치해야 한다. 배치된 각 카드는 그림 2처럼 행과 열의 번호로 구분한다.
그림 2
카드의 초기 배치가 끝나면, 플레이어는 아래에 설명하는 ‘뒤집기’를 필요에 따라 반복한다. 한 번의 ‘뒤집기’는 두 단계로 구성된다.
- 단계 1: 카드가 놓인 $N \times N$ 격자에서 임의의 한 행 또는 한 열을 선택한다. 또한, 카드 A에 적힌 정수 $M$에 따라 임의의 정수 $k(0 \le k < M)$를 선택한다.
- 단계 2: 단계 1에서 선택한 것이 행 $i$라면, $j \equiv k \pmod M$인 모든 $j$에 대해, 격자 상에서 $(i, j)$ 위치에 있는 모든 카드를 뒤집는다. 유사하게, 단계 1에서 선택한 것이 열 $j$라면, $i \equiv k \pmod M$인 모든 $i$에 대해, 격자 상에서 $(i, j)$ 위치에 있는 모든 카드를 뒤집는다.
플레이어는 ‘뒤집기’를 반복해서 격자에 놓인 카드의 패턴과 카드 A에 그려진 패턴 $P$를 일치시켜야 한다. 이것이 실제로 가능한 일인지 판별해보자.
구현 세부 사항
여러분은 아래 함수를 구현해야 한다.
bool reversal(int N, int M, vector<string> P)- 이 함수는 단 한 번만 호출된다.
- 인자로 주어지는 정수 $N$은 격자의 크기를 나타낸다.
- 인자로 주어지는 정수 $M$은 ‘뒤집기’에서 뒤집는 카드의 간격을 나타낸다.
- 인자로 주어지는 배열 $P$는 길이 $N$인 문자열 $N$개로 구성된 배열이며, $P[i]$는 만들어야 하는 패턴의 $i$번 행을 나타낸다.
- 이 함수는 격자에 놓인 초기 배치로부터 ‘뒤집기’를 적용하여 패턴 $P$를 만들 수 있으면
true를, 그렇지 않으면false를 반환해야 한다.
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
데이터 범위
- $1 \le M \le N \le 1000$
- $P$에 속한 모든 문자는 ‘O’ 또는 ‘X’이다.
서브태스크
- (11 점)
- $N \times M \le 10$
- (50 점)
- $M = 1$
- (39 점)
- 추가적인 제약 조건이 없다.
채점 기준
각 서브태스크의 점수는 그 서브태스크의 모든 데이터에 대한 점수 중 최솟값임에 유의하라.
样例
输入格式 1
5 2 XXXOX XXXOX OOOXO XOXXX XOXXX
输出格式 1
true
说明
Sample grader
Sample grader는 아래와 같은 형식으로 입력을 받는다.
N M P[0] P[1] ... P[N-1]
Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.