Problem D
Bar Classification
You are taking a course on machine learning at your university, and as homework you have been tasked with writing a program that can tell vertical bars from horizontal bars in images. To generate some training data, you use the following method. First, take an $N \times N$ grid, and fill it with zeros. Next, take a row or a column, and fill it with ones. Finally, take at most $N$ arbitrary cells, and flip them. Flipping a cell means changing a zero to a one, or changing a one to a zero.
Generating data this way is easy, but how to generate all the answers? It will take hours to go through the training data manually. If only you had a program that finds all the outputs automatically somehow.
You are given an $N \times N$ matrix that has been generated as in the description. Write a program that finds whether it was a column or a row that was filled with ones, or if it is impossible to determine.
Input
The first line of input consists of an integer $N$ ($2 \leq N \leq 1000$), the size of the grid.
The following $N$ lines each contain a string of length $N$ consisting of zeros and ones. These are the rows of the grid.
It is guaranteed that the input was generated by taking a grid of zeros, putting ones on a row or a column, and then flipping at most $N$ cells.
Output
If the bar was vertical (a column), print “|”. If it was horizontal (a row), print “-”. If it is impossible to determine (because it could be both), print “+”.
Sample Input 1 | Sample Output 1 |
---|---|
5 01100 01000 01001 00000 01000 |
| |
Sample Input 2 | Sample Output 2 |
---|---|
3 111 000 111 |
- |
Sample Input 3 | Sample Output 3 |
---|---|
3 010 101 010 |
+ |