Hello All,
I tried solving pylons using the Brute Force approach in which I am
continuously calling the move method for every possible set of cells (i, j)
which are not in same row or column or diagonal.
Here's my piece of code in java but i am getting time limit exceeded for 23
points and test set for 8 points is passed.
package codejam;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Pylon{
/**
* @param args
*/
static int row;
static int col;
static List<List<Integer>> answer = null;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for(int h=1;h<=t;h++)
{
String input[] = br.readLine().split(" ");
row = Integer.parseInt(input[0]);
col = Integer.parseInt(input[1]);
List<List<Integer>> path = new ArrayList<List<Integer>>();
int steps = row*col;
boolean visited[][] = new boolean[row][col];
if(move(0,0,steps,visited,path)){
System.out.println("POSSIBLE");
for(List<Integer> k:answer){
System.out.println(k.get(0)+ " "+k.get(1));
}
}else{
System.out.println("IMPOSSIBLE");
}
}
br.close();
}
// Recursively move to every cell which is valid to move
private static boolean move(int x, int y, int steps, boolean[][]
visited,List<List<Integer>> path) {
if(visited[x][y]){
return false;
}
visited[x][y] =true;
path.add(Arrays.asList(x+1,y+1));
// steps--;
if(steps==1){
answer = path;
return true;
}
boolean found =false;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(isSafe(x, y, i, j) && !visited[i][j]){
if(move(i,j,steps-1,visited,path)){
return true;
}
}
}
}
visited[x][y] = false;
path.remove(path.size()-1);
return found;
}
private static boolean isSafe(int r1, int c1, int r2, int c2) {
return !(r2==r1 || c2==c1 || ((r1-c1)==(r2-c2))|| ((r1+c1)==(r2+c2)));
}
}
Could you please help me to overcome if it can reduce time somewhere?
Regards,
Sudeep
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/a4a7573b-2a4f-45d1-8e97-948b9e9342e2%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
