ACM-ICPC Hanoi 2006-2007- Black-white Grid > 문제은행 : 정보올림피아드&알고리즘



1248 : Black-white Grid

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
7 회   
시도횟수
18 회   

문제

n개의 행과 열로 이루어진 M이라는 격자가 존재한다. 각각의 행과 열은 1부터 n으로 번호가 매겨진다. 

칸(i, j)는 격자안의 i번째 행에 위치한 j번째 열의 칸을 의미한다. 각각의 칸은 검은색 혹은 하얀색으로 칠해져있다. 

C(i, j)를 칸(i, j)의 색이라고 하자. 1≤i≤n에 대해 모든(i, i)를 대각선을 이루는 칸이라고 부르자.



i행과 j행에 대해 행 바꿈을 한다는 것은 1≤k≤n 에 대해 C(i, k)와 C(j, k)를 서로 바꿔주는 것이다. 

이와 유사한 방식으로 열 바꿈 역시 가능하다.



 



M에다 임의적으로 행 바꿈과 열 바꿈을 수행 한 다음 대각선을 이루는 모든 칸이 흰색인 경우가 존재할 때, M에 대해 흰 색칠 가능이라고 한다. 

위의 그림의 경우는 흰 색칠 가능 격자이다.



임의의 n×n 격자가 주어졌을 때, 해당 격자가 흰 색칠 가능한지 아닌지 판단하는 프로그램을 작성하라.

 


입력형식

첫 번째 줄에는 테스트 케이스의 개수 T(T≤100)이 주어진다. 그 다음 줄부터 T개의 격자 정보가 입력되는데, 격자 정보의 첫 번째 줄에는 격자의 크기 N(N≤100)이 입력되고, 그 다음 줄부터 N개의 줄에는 격자의 색깔정보가 입력되는데, 매 줄은 행1, 행2, ... 행N을 입력하고, 각 줄의 문자들은 해당 행의 열의 칸의 색상을 의미한다.

출력형식

테스트 케이스의 순서대로 입력된 격자가 흰 색칠이 가능할 경우 YES를 아닐 경우 NO를 출력한다.

입력 예

2 
3 
WWW 
WBB 
WBB 
3 
BWB 
BWW 
WWB

출력 예

NO
YES


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP