ZOJ Problem Set - 1626
WishingTree, a kind old man, had a large piece of land on which he planted all kinds of trees, apple tree, peach tree, pine, etc. The trees are so well planted that they form a square of n rows and n colomns.
WishingTree, as his name indicated, loved his trees very much. He took good care of the trees and lead on a happy life. Howerever, disaster soon came. A monster called WantingTree wanted to eat his trees. The monster ate nothing but trees, every year, he would went out from his cave and spent k days to fill his stomach up, and then back to sleep again. WantingTree is not a fool, as he knew that mixing diffrent kinds of trees in his stomach may cause complex chemical reaction which might result in poisonous substances, he ate one kind of tree in a year. What's more, he was an efficient monster, each of the k day he chose a single row or column of tree, and ate all the wanted-trees in the row or column. LoveingTree could not fight against WisingTree, but he really thought he could do something. He decided to persuade WantingTree into eating a certain kind of tree, in hope that the number of kinds of his trees is not to decrease, anyway a tree will grow into a forest.
Your are to write a program to figure out which kind of tree can be choose to be eaten by WantingTree, put in another way, WantingTree can not eat all the trees of this kind in k days.
You will be provided these informations:
k: the number of days which WishingTress spent to fill up his stomach. (0 < k < N)
N: the number of rows and columns of the trees (1 < N <= 100)
A matrix of M x N, where Aij denote the tree name of the tree in the i row, j column.
tree name is a single upper case letters from 'A' to 'Z'
First line is a single integer T, specify the number of test cases. each test case begins with a line containg two integer N, K in a single line, followed by N lines describing tree names, each line consists of N upper case letters. There are no space between these letters.
For each test case, print in ascending order all the trees name of which can not be eaten up in k days by WantingTree in a single line. If there is no choice, print "Poor WishingTree!" instead. Print a blank line after each test case.
Author: CHEN Shunbao
Source: ZOJ Monthly, June 2003