To Bee or Not To Bee?
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?
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
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.
For each test case, output a line containing whether or not the garden can be protected from the
bees as a
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.
2 2 xx oo 3 oxo xoo xoo
YES 1 1 1 YES 3 1 1 0 0 2 2