import java.io.*;
import java.util.*;
/**
* Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
*/
//ADD PUBLIC FOR CF,TC
class Node
{
int x,y;
Node(int x1,int y1)
{
x=x1;
y=y1;
}
}
class N1
{
//Datastructures and Datatypes used
static char grid[][];
static int distances[][];
static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
static int dx[]={1,-1,0,0};
static int dy[]={0,0,-1,1};
static Set<Node> points=new HashSet<Node>();
static int flag=1;
{
Scanner sc
=new Scanner
(System.
in); int t=sc.nextInt();//testcases
for(int ixx=0;ixx<t;ixx++)
{
flag=1;
r=sc.nextInt();
if(r==1)
{
sc.next();//Taking in '.' basically
System.
out.
println("0");//Already there continue;
}
c=r;//Rows guarenteed to be same as rows. It a nxn grid
grid=new char[r][c];
distances=new int[r][c];
points.clear();
for(int i=0;i<r;i++)
{
char[]x1=sc.next().toCharArray();
for(int j=0;j<c;j++)
{
grid[i][j]=x1[j];
if(x1[j]=='*')
{
points.add(new Node(i,j));
}
}
}//built grid
s1=s2=0;
distances[s1][s2]=0;//for 0,0
int ansd=0;
while(!points.isEmpty())
{
for(int i=0;i<r;i++)
{
for (int j = 0; j < c; j++)
{
distances[i][j]=0;
if(grid[i][j]=='V')//Visited
{
grid[i][j]='.';
}
}
}
distances[s1][s2]=0;
int dis=BFS();
if(dis!=-1)
{
ansd += dis;//Adding on (minimum?) distaces
//System.out.println("CURR DIS: "+ansd);
}
else
{
flag = 0;
break;
}
}
if(flag==1)
{
for(int i11=0;i11<r;i11++)
{
for(int j1=0;j1<c;j1++)
{
if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
{
grid[i11][j1]='.';
}
distances[i11][j1]=0;
}
}
f1=r-1;f2=c-1;
grid[f1][f2]='*';
int x=BFS();
if(x!=-1)
{
System.
out.
println("ANSWER: "+(ansd
+x
)+"\n");//Final distance }
else
{
System.
out.
println("-1");//Not possible }
}
}
}
public static int BFS()
{
// Printing current grid correctly according to concept
System.
out.
println("SOURCE IS:"+(s1
+1)+","+(s2
+1)); for(int i2=0;i2<r;i2++)
{
for (int j1 = 0; j1 < c; j1++)
{
{
System.
out.
print(grid
[i2
][j1
]); }
}
}
Queue<Node>q=new LinkedList<Node>();
q.add(new Node(s1,s2));
while(!q.isEmpty())
{
Node p=q.poll();
for(int i=0;i<4;i++)
{
if(((p.x+dx[i]>=0)&&(p.x+dx[i]<r))&&((p.y+dy[i]>=0)&&(p.y+dy[i]<c))&&(grid[p.x+dx[i]][p.y+dy[i]]!='#'))
{//If point is in range
int cx,cy;
cx=p.x+dx[i];
cy=p.y+dy[i];
distances[cx][cy]=distances[p.x][p.y]+1;//Distances
if(grid[cx][cy]=='*')//destination
{
for(Node rm:points)// finding the node and removing it
{
if(rm.x==cx&&rm.y==cy)
{
points.remove(rm);
break;
}
}
grid[cx][cy]='.';//It i walkable again
s1=cx;s2=cy;//next source set
return distances[cx][cy];
}
else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
{
grid[cx][cy]='V';//Adding to visited
q.add(new Node(cx,cy));
}
}
}
}
return -1;
}
}
ICAgIGltcG9ydCBqYXZhLmlvLio7CiAgICBpbXBvcnQgamF2YS51dGlsLio7CgogICAgLyoqCiAgICAgKiBDcmVhdGVkIGJ5IFNocmV5YW5zIG9uIDUvMi8yMDE1IGF0IDI6MjkgUE0gdXNpbmcgSW50ZWxsaUogSURFQSAoRmFzdCBJTyBUZW1wbGF0ZSkKICAgICAqLwoKICAgIC8vQUREIFBVQkxJQyBGT1IgQ0YsVEMKICAgIGNsYXNzIE5vZGUKICAgIHsKICAgICAgICBpbnQgeCx5OwogICAgICAgIE5vZGUoaW50IHgxLGludCB5MSkKICAgICAgICB7CiAgICAgICAgICAgIHg9eDE7CiAgICAgICAgICAgIHk9eTE7CiAgICAgICAgfQogICAgfQoKICAgIGNsYXNzIE4xCiAgICB7CiAgICAgICAgLy9EYXRhc3RydWN0dXJlcyBhbmQgRGF0YXR5cGVzIHVzZWQKICAgICAgICBzdGF0aWMgY2hhciBncmlkW11bXTsKICAgICAgICBzdGF0aWMgaW50IGRpc3RhbmNlc1tdW107CiAgICAgICAgc3RhdGljIGludCByPTAsYz0wLHMxPTAsczI9MCxmMT0wLGYyPTA7CiAgICAgICAgc3RhdGljIGludCBkeFtdPXsxLC0xLDAsMH07CiAgICAgICAgc3RhdGljIGludCBkeVtdPXswLDAsLTEsMX07CiAgICAgICAgc3RhdGljIFNldDxOb2RlPiBwb2ludHM9bmV3IEhhc2hTZXQ8Tm9kZT4oKTsKICAgICAgICBzdGF0aWMgaW50IGZsYWc9MTsKCiAgICAgICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uCiAgICAgICAgewogICAgICAgICAgICBTY2FubmVyIHNjPW5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgICAgIGludCB0PXNjLm5leHRJbnQoKTsvL3Rlc3RjYXNlcwogICAgICAgICAgICBmb3IoaW50IGl4eD0wO2l4eDx0O2l4eCsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmbGFnPTE7CiAgICAgICAgICAgICAgICByPXNjLm5leHRJbnQoKTsKICAgICAgICAgICAgICAgIGlmKHI9PTEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc2MubmV4dCgpOy8vVGFraW5nIGluICcuJyBiYXNpY2FsbHkKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIjAiKTsvL0FscmVhZHkgdGhlcmUKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGM9cjsvL1Jvd3MgZ3VhcmVudGVlZCB0byBiZSBzYW1lIGFzIHJvd3MuIEl0IGEgbnhuIGdyaWQKICAgICAgICAgICAgICAgIGdyaWQ9bmV3IGNoYXJbcl1bY107CiAgICAgICAgICAgICAgICBkaXN0YW5jZXM9bmV3IGludFtyXVtjXTsKICAgICAgICAgICAgICAgIHBvaW50cy5jbGVhcigpOwogICAgICAgICAgICAgICAgZm9yKGludCBpPTA7aTxyO2krKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjaGFyW114MT1zYy5uZXh0KCkudG9DaGFyQXJyYXkoKTsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGo9MDtqPGM7aisrKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgZ3JpZFtpXVtqXT14MVtqXTsKICAgICAgICAgICAgICAgICAgICAgICAgaWYoeDFbal09PScqJykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9pbnRzLmFkZChuZXcgTm9kZShpLGopKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0vL2J1aWx0IGdyaWQKICAgICAgICAgICAgICAgIHMxPXMyPTA7CiAgICAgICAgICAgICAgICBkaXN0YW5jZXNbczFdW3MyXT0wOy8vZm9yIDAsMAogICAgICAgICAgICAgICAgaW50IGFuc2Q9MDsKICAgICAgICAgICAgICAgIHdoaWxlKCFwb2ludHMuaXNFbXB0eSgpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGZvcihpbnQgaT0wO2k8cjtpKyspCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGM7IGorKykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgZGlzdGFuY2VzW2ldW2pdPTA7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZihncmlkW2ldW2pdPT0nVicpLy9WaXNpdGVkCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JpZFtpXVtqXT0nLic7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZGlzdGFuY2VzW3MxXVtzMl09MDsKICAgICAgICAgICAgICAgICAgICBpbnQgZGlzPUJGUygpOwogICAgICAgICAgICAgICAgICAgIGlmKGRpcyE9LTEpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBhbnNkICs9IGRpczsvL0FkZGluZyBvbiAobWluaW11bT8pIGRpc3RhY2VzCiAgICAgICAgICAgICAgICAgICAgICAgIC8vU3lzdGVtLm91dC5wcmludGxuKCJDVVJSIERJUzogIithbnNkKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCItMSIpOwogICAgICAgICAgICAgICAgICAgICAgICBmbGFnID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYoZmxhZz09MSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGkxMT0wO2kxMTxyO2kxMSsrKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yKGludCBqMT0wO2oxPGM7ajErKykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICBpZihncmlkW2kxMV1bajFdPT0nVicpLy9UaGVzZSBwbnRzIGJlY29tZSBhY2Nlc2libGUgaW4gdGhlIG5leHQgaXRlcmF0aW9uIGFnYWluCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JpZFtpMTFdW2oxXT0nLic7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaXN0YW5jZXNbaTExXVtqMV09MDsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBmMT1yLTE7ZjI9Yy0xOwogICAgICAgICAgICAgICAgICAgIGdyaWRbZjFdW2YyXT0nKic7CiAgICAgICAgICAgICAgICAgICAgaW50IHg9QkZTKCk7CiAgICAgICAgICAgICAgICAgICAgaWYoeCE9LTEpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkFOU1dFUjogIisoYW5zZCt4KSsiXG4iKTsvL0ZpbmFsIGRpc3RhbmNlCiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiLTEiKTsvL05vdCBwb3NzaWJsZQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcHVibGljIHN0YXRpYyBpbnQgQkZTKCkKICAgICAgICB7CiAgICAgICAgICAgIC8vIFByaW50aW5nIGN1cnJlbnQgZ3JpZCBjb3JyZWN0bHkgYWNjb3JkaW5nIHRvIGNvbmNlcHQKICAgICAgICAgICAgCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiU09VUkNFIElTOiIrKHMxKzEpKyIsIisoczIrMSkpOwogICAgICAgICAgICBmb3IoaW50IGkyPTA7aTI8cjtpMisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqMSA9IDA7IGoxIDwgYzsgajErKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoZ3JpZFtpMl1bajFdKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBRdWV1ZTxOb2RlPnE9bmV3IExpbmtlZExpc3Q8Tm9kZT4oKTsKICAgICAgICAgICAgcS5hZGQobmV3IE5vZGUoczEsczIpKTsKICAgICAgICAgICAgd2hpbGUoIXEuaXNFbXB0eSgpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBOb2RlIHA9cS5wb2xsKCk7CiAgICAgICAgICAgICAgICBmb3IoaW50IGk9MDtpPDQ7aSsrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmKCgocC54K2R4W2ldPj0wKSYmKHAueCtkeFtpXTxyKSkmJigocC55K2R5W2ldPj0wKSYmKHAueStkeVtpXTxjKSkmJihncmlkW3AueCtkeFtpXV1bcC55K2R5W2ldXSE9JyMnKSkKICAgICAgICAgICAgICAgICAgICB7Ly9JZiBwb2ludCBpcyBpbiByYW5nZSAKICAgICAgICAgICAgICAgICAgICAgICAgaW50IGN4LGN5OwogICAgICAgICAgICAgICAgICAgICAgICBjeD1wLngrZHhbaV07CiAgICAgICAgICAgICAgICAgICAgICAgIGN5PXAueStkeVtpXTsKICAgICAgICAgICAgICAgICAgICAgICAgZGlzdGFuY2VzW2N4XVtjeV09ZGlzdGFuY2VzW3AueF1bcC55XSsxOy8vRGlzdGFuY2VzCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGdyaWRbY3hdW2N5XT09JyonKS8vZGVzdGluYXRpb24KICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgZm9yKE5vZGUgcm06cG9pbnRzKS8vIGZpbmRpbmcgdGhlIG5vZGUgYW5kIHJlbW92aW5nIGl0CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYocm0ueD09Y3gmJnJtLnk9PWN5KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9pbnRzLnJlbW92ZShybSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdyaWRbY3hdW2N5XT0nLic7Ly9JdCBpIHdhbGthYmxlIGFnYWluCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBzMT1jeDtzMj1jeTsvL25leHQgc291cmNlIHNldAogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGRpc3RhbmNlc1tjeF1bY3ldOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UgaWYoZ3JpZFtjeF1bY3ldPT0nLicpLy9Ob3JtYWwgdGlsZS4gTm93IHNldHRpbmcgdG8gdmlzaXRlZAogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBncmlkW2N4XVtjeV09J1YnOy8vQWRkaW5nIHRvIHZpc2l0ZWQKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHEuYWRkKG5ldyBOb2RlKGN4LGN5KSk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgIH0KICAgIH0=
SOURCE IS:1,1
...
.##
*#.
SOURCE IS:3,1
...
.##
.#*
-1
SOURCE IS:1,1
..*
...
...
SOURCE IS:1,3
...
...
..*
ANSWER: 4
SOURCE IS:1,1
..*
*..
...
SOURCE IS:2,1
..*
...
...
SOURCE IS:1,3
...
...
..*
ANSWER: 6
SOURCE IS:1,1
....
.#.*
.#*.
**#.
SOURCE IS:4,1
....
.#.*
.#*.
.*#.
SOURCE IS:4,2
....
.#.*
.#*.
..#.
SOURCE IS:3,3
....
.#.*
.#..
..#.
SOURCE IS:2,4
....
.#..
.#..
..#*
ANSWER: 16