using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
// Algorithm explanation:
//
// Suppose we have a grid like
//
// . . X
// . . .
// * X M
//
// Since we can travel along the the dots any distance in a
// single move, a graph of the possible moves is like
//
// (0,0) -------- (1,0)
// / \ |
// / \ |
// (0,2)---(0,1) --- (1,1)
// \ /
// \ /
// \ /
// (2,1)
// /
// /
// (2,2)
//
// where the distance between every node is 1. We're trying to get
// from node (2,2) to node (0,2) in the shortest route. We can use
// a BFS to find this route.
class Node
{
// coordinates
public int X { get; set; }
public int Y { get; set; }
// parent node
public Node Parent { get; set; } = null;
// distance from root node
public int Distance { get; set; } = Int32.MaxValue; // "infinity"
// nodes connected to this one
public List<Node> Neighbors { get; set; } = new List<Node>();
}
class ForbiddenForest
{
private Node[,] _tree;
private Node _start;
private Node _end;
public ForbiddenForest(char[,] mat)
{
BuildTree(mat);
}
// helper method for traversing a 2-D array
private static IEnumerable<T> MultiElements<T>(T[,] source)
{
for(int i = 0, n = source.GetLength(0); i < n; ++i)
for(int j = 0, m = source.GetLength(1); j < m; ++j)
yield return source[i, j];
}
private void BuildTree(char[,] mat)
{
int m = mat.GetLength(0),
n = mat.GetLength(1);
_tree = new Node[m, n];
// Add all the nodes to the tree with their x-y positions.
// Set the start and end nodes when we come across them.
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
switch(mat[i, j])
{
case '.':
_tree[i, j] = new Node() { X = i, Y = j };
break;
case 'M':
_tree[i, j] = new Node() { X = i, Y = j };
_start = _tree[i, j];
break;
case '*':
_tree[i, j] = new Node() { X = i, Y = j };
_end = _tree[i, j];
break;
}
}
}
var nodes = MultiElements(_tree).Where(z => z != null);
// Now add the neighbors. To do this, start at the node's x-y
// position on the graph and move as far possible up, right,
// down and left, collecting the nodes as we move along.
foreach(var node in nodes)
{
int x = node.X, y = node.Y;
// up:
while (--y >= 0 && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
// right:
y = node.Y;
while (++x < m && _tree[y, y] != null)
node.Neighbors.Add(_tree[x, y]);
// down:
x = node.X;
while (++y < n && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
// left:
y = node.Y;
while (--x >= 0 && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
}
// Now fill in the Distance and Parent values by using the BFS
// algorithm on https://en.wikipedia.org/wiki/Breadth-first_search
var Q = new Queue<Node>();
_start.Distance = 0;
Q.Enqueue(_start);
while(Q.Count > 0)
{
var current = Q.Dequeue();
foreach(var neighbor in current.Neighbors)
{
if(neighbor.Distance == Int32.MaxValue)
{
neighbor.Distance = current.Distance + 1;
neighbor.Parent = current;
Q.Enqueue(neighbor);
}
}
} }
public int OptimalMoveNumbers { get { return _end.Distance; } }
}
class Solution
{
static void Main(String[] args)
{
int T = Int32.Parse(Console.ReadLine());
for(int t = 0; t < T; ++t)
{
int[] line = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int N = line[0], M = line[1];
char[,] matrix = new char[M,N];
for(int i = 0; i < N; ++i)
{
char[] row = Console.ReadLine().Where(c => c != ' ').ToArray();
for(int j = 0; j < M; ++j)
matrix[j,i] = row[j];
}
int K = Int32.Parse(Console.ReadLine());
var ff = new ForbiddenForest(matrix);
Console.WriteLine(K == ff.OptimalMoveNumbers() ? "Impressed" : "Oops!");
}
}
}