Graph Traversal

• Tweet
• 

        // Graph traversal

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/*
ID: kanishk1
LANG: JAVA
TASK: skate
*/

import java.util.*;
import java.io.*;

public class skate {
	 static char [][]arr;
	 static ArrayList list = new ArrayList();
	 static PrintWriter out;
	 public static void main (String [] args) throws IOException {
	    // Use BufferedReader rather than RandomAccessFile; it's much faster
	    BufferedReader f = new BufferedReader(new FileReader("skate.in"));
	                                                  // input file name goes above
	    out = new PrintWriter(new BufferedWriter(new FileWriter("skate.out")));
	    // Use StringTokenizer vs. readLine/split -- lots faster
	    StringTokenizer st = new StringTokenizer(f.readLine());
	    int R = Integer.parseInt(st.nextToken());   
	    int C = Integer.parseInt(st.nextToken());   
	    //System.out.println(R+" "+C);
	    arr = new char[R][C];
	    for(int i=0; i<R; i++) {
	    	arr[i] = f.readLine().trim().toCharArray();
	    }
	    list.add(pair(0,0));
	    doTask(0, 0);
	  }		  
	 
	 private static void doTask(int i, int j) {
		 //System.out.println(pair(i,j));
		 if(i==arr.length-1 && j==arr[0].length-1) {
			 //System.out.println("here"); 
			 out.println(printAnswer(list));                        
			 out.close();                                 
			 System.exit(0); 
		 }
		 if(isValid(i+1, j)) {
			 list.add(pair(i+1,j));
			 arr[i+1][j] = '@';
			 doTask(i+1,j);
			 arr[i+1][j] = '.';
			 list.remove(pair(i+1,j));
		 }
		 if(isValid(i-1, j)) {
			 list.add(pair(i-1,j));
			 arr[i-1][j] = '@';
			 doTask(i-1,j);
			 arr[i-1][j] = '.';
			 list.remove(pair(i-1,j));
		 }
		 if(isValid(i, j+1)) {
			 arr[i][j+1] = '@';
			 list.add(pair(i,j+1));
			 doTask(i,j+1);
			 arr[i][j+1] = '.';
			 list.remove(pair(i,j+1));
		 }
		 if(isValid(i, j-1)) {
			 arr[i][j-1] = '@';
			 list.add(pair(i,j-1));
			 doTask(i,j-1);
			 arr[i][j-1] = '.';
			 list.remove(pair(i,j-1));
		 }
		 return;
	 }
	 
	 private static boolean isValid(int i, int j) {
		 if(i<0 || j<0 || i>=arr.length || j>=arr[0].length) return false;
		 if(arr[i][j]!='.') return false;
		 return true;
	 }
	 
	 private static String pair(int i, int j) {
		 return (i+1)+" "+(j+1);
	 }
	 
	 private static String printAnswer(ArrayList list) {
		 String ans = "";
		 for(int i=0; i<list.size(); i++) {
			 ans+=list.get(i);
			 if(i!=list.size()-1) ans+="\n";
		 }
		 return ans;
	 }
}

Tags:
• graph
• java