To Bee or Not To Bee?


Submit solution

Points: 1
Time limit: 3.0s
Memory limit: 512M

Authors:
Problem types

A flower garden is having all of it's visitors chased away by particularly unfriendly bees. In order to combat this problem in the most unfriendly way possible, the gardeners have chosen to set up a series of laser cannons to keep the bees away. The lasers can shoot in each of the cardinal directions for infinite distances or until it hits one of the many statues in the garden. A laser placed in a statue will hit that statue, and travel nowhere. The flower garden can be seen as an \(N\) by \(N\) grid and each non-statue square in this grid must be protected. The garden contains \(B\) statues and the gardeners have access to \(2B\) laser cannons. Due to gardening related reasons, it is guaranteed that the number of statues is at least \(N\); thus it is guaranteed that \(N\leq B \leq N^2\).

Is it possible for the gardeners to protect the garden from the bees? And if so, where should they place the laser cannons in order to do so?

Input Specification

The first line contains an integer \(T\) (\(1\leq T \leq 10\)), the number of test cases to follow. Each test case begins with a line containing two integers, \(N\) (\(1\leq N \leq 500\)) , the side length of the flower garden. Following this in each test case will be \(N\) lines. Each line will be a string containing o and x characters. If the \(c\)th character on the \(r\)th line is x, then the garden grid has a statue on the \(r\)th row and \(c\)th column. It is guaranteed that the number of x characters, \(B\), will be at least \(N\).

Note: This problem has a lot of input. Please use fast I/O.

Output Specification

For each test case, output a line containing whether or not the garden can be protected from the bees as a YES or NO response. Also, if the answer is YES, the next line should contain a single integer, \(C\), the number of laser cannons that you will use, and each of the \(C\) following lines should contain the row and column coordinates of your laser cannons. Note that your coordinates must be zero indexed, and the top left corner is considered to be row 0 column 0. Any valid laser cannon placement strategy will be considered correct. You will receive wrong answer if \(C>2B\), your output does not meet specifications, or if you failed to cover every non-statue location in the grid.

Sample Input

2
2
xx
oo
3
oxo
xoo
xoo

Sample Output

YES
1
1 1
YES
3
1 1
0 0
2 2

Comments

There are no comments at the moment.