Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
983. Grid
Поиск в глубину (DFS)Олимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание ( 6I) |
| 14/07/2008 | Лето 2008 - 6 (I) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Let `M` be a grid of `n` rows and `n` columns. The rows are numbered from 1 to `n` and the columns are numbered from 1 to `n`. A cell `(i,\ j)` denotes the cell in row `i` and column `j` in the grid. Each cell is colored in black or white. Let `C_{ij}` denote the color of the cell `(i,\ j)`. All cells of the form `(i,\ i)` for `1\ ≤\ i\ ≤\ n` are called diagonal cells.
Swapping rows `i` and `j` of the grid `M` denotes the following action: we swap the values of `C_"ik"` and `C_"jk"` for `k\ =\ 1,\ 2,\ …,\ n`. Swapping two columns is defined analogously.
We say that `M` is white-colorable if it is possible to swap some of the pairs of rows and some of the pairs of columns (in any sequence) so that, after all the swappings, all the diagonal cells of `M` are white.
Your task is to write a program that determines whether given grid `M` is white-colorable.
Input
The first line contains a single positive integer `n` (`n\ ≤\ 1000`) – the size of the grid. The `i`-th line of the following `n` lines contains `n` characters `C_{ij}` (`i=1,\ 2,\ …,\ n`; `j=1,\ 2,\ …,\ n`) specifying color pattern of the grid. Character `C_{ij}` is 'B' or 'W' indicating that the color of cell `(i,\ j)` is black or white respectively.
Output
Write "YES" if given grid is white-colorable or "NO" otherwise.
Sample Input 1
3 WWW WBB WBB
Sample Output 1
NO
Sample Input 2
3 BWB BWW WWB
Sample Output 2
YES
