We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
publicstaticStringcountLuck(List<String>matrix,intk){// Write your code hereList<Integer>start=getStartIndex(matrix);Map<String,Integer>map=newHashMap<>();map.put("counter",0);isSolution(start.get(0),start.get(1),matrix,newHashSet<>(),map);returnmap.get("counter")==k?"Impressed":"Oops!";}privatestaticList<Integer>getStartIndex(List<String>matrix){for(inti=0;i<matrix.size();i++)if(matrix.get(i).contains("M"))returnArrays.asList(i,matrix.get(i).indexOf("M"));returnnull;}privatestaticbooleanisSolution(inti,intj,List<String>matrix,Set<String>visited,Map<String,Integer>map){if(visited.contains(i+","+j))returnfalse;visited.add(i+","+j);if(!isValidIndex(i,j,matrix))returnfalse;if(matrix.get(i).charAt(j)=='X')returnfalse;if(matrix.get(i).charAt(j)=='*')returntrue;intcount=0;if(isCellValid(i-1,j,matrix,visited))count++;if(isCellValid(i,j-1,matrix,visited))count++;if(isCellValid(i+1,j,matrix,visited))count++;if(isCellValid(i,j+1,matrix,visited))count++;if(count>1){map.put("counter",map.get("counter")+1);}//Backtrack and add the counts in sub path (i.e. if the correct path)Map<String,Integer>localMap=newHashMap<>();localMap.put("counter",0);if(isSolution(i-1,j,matrix,visited,localMap)){//topmap.put("counter",map.get("counter")+localMap.get("counter"));returntrue;}else{localMap=newHashMap<>();localMap.put("counter",0);if(isSolution(i,j-1,matrix,visited,localMap)){//leftmap.put("counter",map.get("counter")+localMap.get("counter"));returntrue;}else{localMap=newHashMap<>();localMap.put("counter",0);if(isSolution(i+1,j,matrix,visited,localMap)){//bottommap.put("counter",map.get("counter")+localMap.get("counter"));returntrue;}else{localMap=newHashMap<>();localMap.put("counter",0);if(isSolution(i,j+1,matrix,visited,localMap)){map.put("counter",map.get("counter")+localMap.get("counter"));returntrue;}}}}returnfalse;}privatestaticbooleanisCellValid(inti,intj,List<String>matrix,Set<String>visited){if(visited.contains(i+","+j))returnfalse;if(!isValidIndex(i,j,matrix))returnfalse;returnmatrix.get(i).charAt(j)=='.'||matrix.get(i).charAt(j)=='*';}privatestaticbooleanisValidIndex(inti,intj,List<String>matrix){returni>=0&&j>=0&&i<matrix.size()&&j<matrix.get(0).length();}
Count Luck
You are viewing a single comment's thread. Return to all comments →
Java Solution