fork download
copy 
  1. /* package workspace; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. public class Main
  9. {
  10.     static List<Integer> minSeen = new ArrayList<Integer>();
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13. 		Scanner sc = new Scanner(System.in);
  14. 		int t = sc.nextInt();
  15. 		for(int i=0;i<t;i++) {
  16. 		    int n = sc.nextInt();
  17. 		    int m = sc.nextInt();
  18. 		    char[][] arr = new char[n][m];
  19. 		    sc.nextLine();
  20. 		    int startI = -1;
  21. 		    int startJ = -1;
  22. 		    for(int j=0;j<n;j++) {
  23. 		        int count=0;
  24. 		        String str = sc.nextLine();
  25.  
  26. 		        StringTokenizer tok = new StringTokenizer(str, " ");
  27. 		        while(tok.hasMoreTokens()) {
  28. 		            String s = tok.nextToken();
  29. 		            arr[j][count++] = s.charAt(0);
  30. 		            if(s.charAt(0) == 'B') {
  31. 		                startI = j;
  32. 		                startJ = m-1;
  33. 		            }
  34. 		        }
  35. 		    }
  36. 		    Map<String, Boolean> tracker = new HashMap<String, Boolean>();
  37. 		    catchP(arr, tracker, 0, n, m, startI, startJ);
  38. 		    // find min over minSeen here.
  39. 		    int min = Integer.MAX_VALUE;
  40. 		    for(Integer minI : minSeen) {
  41. 		        if( min > minI) {
  42. 		            min = minI;
  43. 		        }
  44. 		    }
  45. 		    System.out.println(min);
  46. 		}
  47. 	}
  48.  
  49. 	static boolean seenAlready(Map<String, Boolean> tracker, int n, int m) {
  50. 	    String key = Integer.toString(n) + "." + Integer.toString(m);
  51. 	    return tracker.containsKey(key);
  52. 	}
  53.  
  54. 	static boolean isValid(int row, int col, int n, int m) {
  55. 	    if( row >= 0 && row <= n-1 && col >=0 && col <= m-1) {
  56. 	        return true;
  57. 	    }
  58. 	    return false;
  59. 	}
  60.  
  61. 	static void catchP(char[][] arr, Map<String, Boolean> tracker, int len, int n, int m, int startI, int startJ) {
  62. 	    Map<String, Boolean> currentTracker = new HashMap<String, Boolean>();
  63. 	    if(arr[startI][startJ] == 'C') {
  64. 	        minSeen.add(len);
  65. 	    } else if ( arr[startI][startJ] == 'D' || arr[startI][startJ]=='.' && seenAlready(tracker, startI, startJ) ) {
  66. 	        return;
  67. 	    } else if ( arr[startI][startJ]=='.' && !seenAlready(tracker, startI, startJ) || arr[startI][startJ] == 'B' ) {
  68. 	        // copy currentTracker same as tracker.
  69. 	        tracker.forEach(currentTracker::putIfAbsent);
  70. 	        String newKey = Integer.toString(startI) + "." + Integer.toString(startJ);
  71. 	        currentTracker.put(newKey, true);
  72. 	        if( isValid(startI, startJ-1, n, m)) {
  73. 	            catchP(arr, currentTracker, len+1, n, m, startI, startJ-1);
  74. 	        }
  75. 	        if( isValid(startI-1, startJ, n , m)) {
  76. 	            catchP(arr, currentTracker, len+1, n, m, startI-1, startJ);
  77. 	        }
  78. 	        if( isValid(startI, startJ+1, n, m) ) {
  79. 	            catchP(arr, currentTracker, len+1, n, m, startI, startJ+1);
  80. 	        }
  81. 	        if( isValid(startI+1, startJ, n, m) ) {
  82. 	            catchP(arr, currentTracker, len+1, n, m, startI+1, startJ);
  83. 	        }
  84. 	    }
  85. 	}
  86. }
  87.  
Success #stdin #stdout 0.1s 712192KB
comments (?)
stdin
copy 
1
3
3
. . B
D . .
. C .
stdout
copy 
3
https://ideone.com/VwPx5y
language:
Java (HotSpot 12)
created:
8 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!