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.
I don't understand the issue with my code, I am probably missing some mathematical shortcut to the problem, can someone please guide me in finding the correct solution. Also, is this a kind of problem that someone can ask in an interview? I don't think I would know how to tackle a problem like this in 15 mins.
My Code (with a lot of commented parts for printing and checking result for debugging):
importjava.io.*;importjava.util.*;importjava.text.*;importjava.math.*;importjava.util.regex.*;publicclassSolution{privatestaticfinalintkModulo=1000000007;publicstaticvoidmain(Stringargs[])throwsException{/* Enter your code here. Read input from STDIN. Print output to STDOUT */Scannerscan=newScanner(System.in);intT=scan.nextInt();for(inti=0;i<T;i++){intN=scan.nextInt();intM=scan.nextInt();boolean[][]grid=newboolean[N][M];for(intj=0;j<N;j++){Stringrow=scan.next();for(intk=0;k<M;k++){grid[j][k]=row.charAt(k)=='#';}}//printGrid(grid, N, M);System.out.println(numberOfWaysToFillGrid(grid,N,M,0,0));}}privatestaticbooleancheckIfPossible(boolean[][]grid,intN,intM){intcount=0;intcountCol[]=newint[M];for(intj=0;j<N;j++){intcountRow=0;for(intk=0;k<M;k++){if(!grid[j][k]){count++;}}}if(count%4!=0){System.out.println(0);continue;}}privatestaticvoidprintGrid(boolean[][]grid,intN,intM){for(inti=0;i<N;i++){for(intj=0;j<M;j++){System.out.print(grid[i][j]);}System.out.print("\n");}}privatestaticvoidprintMatrix(int[][]grid,intN,intM){for(inti=0;i<N;i++){for(intj=0;j<M;j++){System.out.print(grid[i][j]);}System.out.print("\n");}}privatestaticintnumberOfWaysToFillGrid(boolean[][]grid,intN,intM,intstartRow,intstartCol){intnumberOfWays=0;intunfilledTileRow=-1;intunfilledTileCol=-1;for(inti=startRow;i<N&&unfilledTileRow<0;i++){for(intj=startRow==i?startCol:0;j<M;j++){if(grid[i][j]==false){// Found unfilled tileunfilledTileRow=i;unfilledTileCol=j;//System.out.println("Found Ya " + i + "," + j);break;}}}if(unfilledTileRow==-1&&unfilledTileCol==-1){//System.out.print("Worked: ");//printGrid(grid, N, M);return1;}//System.out.println(unfilledTileRow + "," + unfilledTileCol);for(intorientation=0;orientation<8;orientation++){booleanfillTile=fillTile(grid,N,M,unfilledTileRow,unfilledTileCol,orientation);//System.out.println(unfilledTileRow + "," + unfilledTileCol + ":" + orientation + "=" + fillTile);if(fillTile){intnumberOfWaysNew=numberOfWaysToFillGrid(grid,N,M,unfilledTileRow,unfilledTileCol);numberOfWays+=numberOfWaysNew;//if (numberOfWaysNew > 0) {//System.out.println("Works: " + unfilledTileRow + "," + unfilledTileCol + ":" + orientation + "=" + numberOfWays);//}removeTile(grid,N,M,unfilledTileRow,unfilledTileCol,orientation);}}returnnumberOfWays%kModulo;}privatestaticfinalint[][][]orientations={{{0,0},{1,0},{2,0},{2,1}},{{0,0},{1,0},{0,1},{0,2}},{{0,0},{0,1},{1,1},{2,1}},{{0,0},{1,0},{1,-1},{1,-2}},{{0,0},{1,0},{2,0},{2,-1}},{{0,0},{1,0},{1,1},{1,2}},{{0,0},{0,1},{1,0},{2,0}},{{0,0},{0,1},{0,2},{1,2}}};privatestaticbooleanfillTile(boolean[][]grid,intN,intM,intindexRow,intindexCol,intorientation){intorientationMatrix[][]=orientations[orientation];intcurrentMatrix[][]=newint[4][2];for(inti=0;i<4;i++){currentMatrix[i][0]=orientationMatrix[i][0]+indexRow;currentMatrix[i][1]=orientationMatrix[i][1]+indexCol;if(currentMatrix[i][0]<0||currentMatrix[i][0]>=N||currentMatrix[i][1]<0||currentMatrix[i][1]>=M||grid[currentMatrix[i][0]][currentMatrix[i][1]]==true){returnfalse;}}/*System.out.print("Orientation " + orientation + ":\n"); printMatrix(orientationMatrix, 4, 2); System.out.print("Matrix: \n"); printMatrix(currentMatrix, 4, 2);*/for(inti=0;i<4;i++){grid[currentMatrix[i][0]][currentMatrix[i][1]]=true;}returntrue;}privatestaticvoidremoveTile(boolean[][]grid,intN,intM,intindexRow,intindexCol,intorientation){intorientationMatrix[][]=orientations[orientation];intcurrentMatrix[][]=newint[4][2];for(inti=0;i<4;i++){currentMatrix[i][0]=orientationMatrix[i][0]+indexRow;currentMatrix[i][1]=orientationMatrix[i][1]+indexCol;grid[currentMatrix[i][0]][currentMatrix[i][1]]=false;}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Brick Tiling
You are viewing a single comment's thread. Return to all comments →
I don't understand the issue with my code, I am probably missing some mathematical shortcut to the problem, can someone please guide me in finding the correct solution. Also, is this a kind of problem that someone can ask in an interview? I don't think I would know how to tackle a problem like this in 15 mins. My Code (with a lot of commented parts for printing and checking result for debugging):