fork download
copy 
  1.     import java.io.*;
  2.     import java.util.*;
  3.  
  4.     /**
  5.      * Created by Shreyans on 5/2/2015 at 2:29 PM using IntelliJ IDEA (Fast IO Template)
  6.      */
  7.  
  8.     //ADD PUBLIC FOR CF,TC
  9.     class Node
  10.     {
  11.         int x,y;
  12.         Node(int x1,int y1)
  13.         {
  14.             x=x1;
  15.             y=y1;
  16.         }
  17.     }
  18.  
  19.     class N1
  20.     {
  21.         //Datastructures and Datatypes used
  22.         static char grid[][];
  23.         static int distances[][];
  24.         static int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
  25.         static int dx[]={1,-1,0,0};
  26.         static int dy[]={0,0,-1,1};
  27.         static Set<Node> points=new HashSet<Node>();
  28.         static int flag=1;
  29.  
  30.         public static void main(String[] args) throws IOException
  31.         {
  32.             Scanner sc=new Scanner(System.in);
  33.             int t=sc.nextInt();//testcases
  34.             for(int ixx=0;ixx<t;ixx++)
  35.             {
  36.                 flag=1;
  37.                 r=sc.nextInt();
  38.                 if(r==1)
  39.                 {
  40.                     sc.next();//Taking in '.' basically
  41.                     System.out.println("0");//Already there
  42.                     continue;
  43.                 }
  44.                 c=r;//Rows guarenteed to be same as rows. It a nxn grid
  45.                 grid=new char[r][c];
  46.                 distances=new int[r][c];
  47.                 points.clear();
  48.                 for(int i=0;i<r;i++)
  49.                 {
  50.                     char[]x1=sc.next().toCharArray();
  51.                     for(int j=0;j<c;j++)
  52.                     {
  53.                         grid[i][j]=x1[j];
  54.                         if(x1[j]=='*')
  55.                         {
  56.                             points.add(new Node(i,j));
  57.                         }
  58.                     }
  59.                 }//built grid
  60.                 s1=s2=0;
  61.                 distances[s1][s2]=0;//for 0,0
  62.                 int ansd=0;
  63.                 while(!points.isEmpty())
  64.                 {
  65.                     for(int i=0;i<r;i++)
  66.                     {
  67.                         for (int j = 0; j < c; j++)
  68.                         {
  69.                             distances[i][j]=0;
  70.                             if(grid[i][j]=='V')//Visited
  71.                             {
  72.                                 grid[i][j]='.';
  73.                             }
  74.                         }
  75.                     }
  76.                     distances[s1][s2]=0;
  77.                     int dis=BFS();
  78.                     if(dis!=-1)
  79.                     {
  80.                         ansd += dis;//Adding on (minimum?) distaces
  81.                         //System.out.println("CURR DIS: "+ansd);
  82.                     }
  83.                     else
  84.                     {
  85.                         System.out.println("-1");
  86.                         flag = 0;
  87.                         break;
  88.                     }
  89.                 }
  90.                 if(flag==1)
  91.                 {
  92.                     for(int i11=0;i11<r;i11++)
  93.                     {
  94.                         for(int j1=0;j1<c;j1++)
  95.                         {
  96.                            if(grid[i11][j1]=='V')//These pnts become accesible in the next iteration again
  97.                             {
  98.                                 grid[i11][j1]='.';
  99.                             }
  100.                             distances[i11][j1]=0;
  101.                         }
  102.                     }
  103.                     f1=r-1;f2=c-1;
  104.                     grid[f1][f2]='*';
  105.                     int x=BFS();
  106.                     if(x!=-1)
  107.                     {
  108.                         System.out.println("ANSWER: "+(ansd+x)+"\n");//Final distance
  109.                     }
  110.                     else
  111.                     {
  112.                         System.out.println("-1");//Not possible
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.  
  118.         public static int BFS()
  119.         {
  120.             // Printing current grid correctly according to concept
  121.  
  122.             System.out.println("SOURCE IS:"+(s1+1)+","+(s2+1));
  123.             for(int i2=0;i2<r;i2++)
  124.             {
  125.                 for (int j1 = 0; j1 < c; j1++)
  126.                 {
  127.                     {
  128.                         System.out.print(grid[i2][j1]);
  129.                     }
  130.                 }
  131.                 System.out.println();
  132.             }
  133.             Queue<Node>q=new LinkedList<Node>();
  134.             q.add(new Node(s1,s2));
  135.             while(!q.isEmpty())
  136.             {
  137.                 Node p=q.poll();
  138.                 for(int i=0;i<4;i++)
  139.                 {
  140.                     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]]!='#'))
  141.                     {//If point is in range 
  142.                         int cx,cy;
  143.                         cx=p.x+dx[i];
  144.                         cy=p.y+dy[i];
  145.                         distances[cx][cy]=distances[p.x][p.y]+1;//Distances
  146.                         if(grid[cx][cy]=='*')//destination
  147.                         {
  148.                             for(Node rm:points)// finding the node and removing it
  149.                             {
  150.                                 if(rm.x==cx&&rm.y==cy)
  151.                                 {
  152.                                     points.remove(rm);
  153.                                     break;
  154.                                 }
  155.                             }
  156.                             grid[cx][cy]='.';//It i walkable again
  157.                             s1=cx;s2=cy;//next source set
  158.                             return distances[cx][cy];
  159.                         }
  160.                         else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
  161.                         {
  162.                             grid[cx][cy]='V';//Adding to visited
  163.                             q.add(new Node(cx,cy));
  164.                         }
  165.                     }
  166.                 }
  167.             }
  168.             return -1;
  169.         }
  170.     }
Success #stdin #stdout 0.15s 321088KB
comments (?)
stdin
copy 
4

3
...
.##
*#.

3
..*
...
...

3
..*
*..
...

4
....
.#.*
.#*.
**#.
stdout
copy 
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
https://ideone.com/qoE859
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!