OJ Board

Code: Select all

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

public class Wheels {
	public static void main(String[] args) throws IOException{
		BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(inp.readLine());
		while(test>0){
			String start = inp.readLine();
			StringTokenizer sm = new StringTokenizer(start," ");
			String temp = new String("");
			while(sm.hasMoreTokens()){
				temp = temp+sm.nextToken();	
			}
			int st = Integer.parseInt(temp);
			String end = inp.readLine();
			StringTokenizer sm2 = new StringTokenizer(end," ");
			String temp2 = new String("");
			while(sm2.hasMoreTokens()){
				temp2 = temp2 + sm2.nextToken();
			}
			int en = Integer.parseInt(temp2);
			int f = Integer.parseInt(inp.readLine());
			int forbid[] = new int[f];
			int i =0;
			while(i<f){
				String temp3 = new String("");
				StringTokenizer z = new StringTokenizer(inp.readLine()," ");
				while(z.hasMoreTokens()){
					temp3 = temp3+z.nextToken();
				}
				forbid[i] = Integer.parseInt(temp3);
				i++;		
			}
			System.out.println(compute(st,en,forbid));
			if(test!=1){
				String s = inp.readLine();
			}
			test--;
		}
	}

	public static int compute(int st, int end, int[] forbid){
		if(st==end) return 0;
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.offer(st);
		HashMap<Integer,Boolean> discovered = new HashMap<Integer,Boolean>();
		discovered.put(st,true);
		HashMap<Integer,Integer> cost = new HashMap<Integer,Integer>();
		cost.put(st,0);
		while(!q.isEmpty()){

			int current = q.poll();
			int k = 0;
			int[] child = construct(current);
			while(k<8){
				if(child[k]==end)return cost.get(current)+1;
				if(!search(forbid,child[k])){
					if(!discovered.containsKey(child[k])){
						discovered.put(child[k],true);
						q.offer(child[k]);
						cost.put(child[k],cost.get(current)+1);
					}
				}
				k++;
			}
		}
		return -1;
	}

	public static boolean search(int[] forbid,int val){
		for(int i =0;i<forbid.length;i++){
			if(forbid[i]==val) return true;
		}
		return false;
	}

	public static int[] construct(int current){
		int res[] = new int[8];
		int digs[] = new int[4];
		digs[3] = current%10;
		int temp = (current%100);
		digs[2] = temp/10;
		digs[1] = (current%1000)/100;
		digs[0] = (current%10000)/1000;

		if(digs[0]==9) {
			res[0] = digs[1]*100 + digs[2]*10 + digs[3];
		}
		else{
			res[0] = (digs[0]+1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		if(digs[1]==9) {
			res[1] = digs[0]*1000 + digs[2]*10 + digs[3];
		}
		else{
			res[1] = (digs[1]+1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
		}
		if(digs[2]==9) {
			res[2] = digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
		}
		else{
			res[2] = digs[0]*1000 + digs[1]*100 + (digs[2]+1)*10 + digs[3];
		}
		if(digs[3]==9) {
			res[3] = digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
		}
		else{
			res[3] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]+1;
		}


		if(digs[0]==0) {
			res[4] = 9000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		else{
			res[4] = (digs[0]-1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
		}
		if(digs[1]==0) {
			res[5] = digs[0]*1000 + digs[2]*10 + digs[3]+900;
		}
		else{
			res[5] = (digs[1]-1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
		}
		if(digs[2]==0) {
			res[6] = 90+digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
		}
		else{
			res[6] = digs[0]*1000 + digs[1]*100 + (digs[2]-1)*10 + digs[3];
		}
		if(digs[3]==0) {
			res[7] = 9+digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
		}
		else{
			res[7] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]-1;
		}
		return res;

	}
}

Code: Select all

10
9 9 9 9
9 9 9 9
1
9 9 9 9

9 9 9 9
0 0 0 0
1
0 0 0 0

9 9 9 9
0 0 0 0
1
9 9 9 9

3 3 4 2
1 2 0 9
1
3 4 4 2

9 9 9 9
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

9 9 9 9
0 0 1 1
3
8 9 0 7
6 5 4 2
2 3 4 5

0 0 0 0
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
6 5 7 9
8 5 7 9

1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
0 0 0 0
8 5 7 9

1 7 1 0
7 0 0 0
6
1 9 0 7
1 4 2 2
1 3 4 5
4 4 4 4
2 5 0 9
1 1 7 9

Code: Select all

0
-1
4
10
5
6
1
11
11
8

Code: Select all

-1
-1
-1
10
5
6
1
11
11
8

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

class Main {
  public static int COMBINATIONS = 10000;

  static class Graph {
    public EdgeNode[] edges;
    public boolean[] invalid;
    public boolean[] discovered;
    public int[] parent;

    class EdgeNode {
      public Integer y;
      public EdgeNode next;

      public EdgeNode(Integer y) {
        this.y = y;
      }
    }

    public Graph() {
      edges = new EdgeNode[COMBINATIONS];
      parent = new int[COMBINATIONS];
      invalid = new boolean[COMBINATIONS];
      discovered = new boolean[COMBINATIONS];

      for (int i = 0; i < COMBINATIONS; i++) {
        List<Integer> neighbors = getNeighbors(i);
        Iterator<Integer> it = neighbors.iterator();

        while (it.hasNext()) {
          insertEdge(i, it.next(), true);
        }
      }
    }

    public void bfs(int start) {
      int v, y;
      EdgeNode p;

      for (int i = 0; i < COMBINATIONS; i++) {
        parent[i] = -1;
        discovered[i] = false;
      }

      LinkedList<Integer> queue = new LinkedList<Integer>();
      queue.add(start);
      discovered[start] = true;

      while (!queue.isEmpty()) {
        v = queue.pollLast();
        p = this.edges[v];

        while (p != null) {
          y = p.y;
          if (!invalid[y] && !discovered[y]) {
            queue.push(y);
            discovered[y] = true;
            parent[y] = v;
          }
          p = p.next;
        }
      }
    }

    public int findPath(int start, int end) {
      if ((start == end) || (end == -1)) {
        return 0;
      } else {
        return 1 + findPath(start, parent[end]);
      }
    }

    private void insertEdge(int x, int y, boolean directed) {
      EdgeNode node = new EdgeNode(y);
      node.next = this.edges[x];
      this.edges[x] = node;
    }

    private List<Integer> getNeighbors(Integer combination) {
      List<Integer> neighbors = new LinkedList<Integer>();
      int digit, temp = combination;

      for (int i = 0; i < 4; i++) {
        digit = temp % 10;
        temp = temp / 10;

        if (digit == 0) {
          neighbors.add(combination + 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        } else if (digit == 9) {
          neighbors.add(combination - 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) -Math.pow(10, i));
        } else {
          neighbors.add(combination + (int) -Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        }
      }

      return neighbors;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int cases = Integer.parseInt(br.readLine().trim()), invalidCases = 0, source = 0, destination = 0;
    Graph graph = new Graph();

    for (int y = 0; y < cases; y++) {

      source = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));
      destination = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      invalidCases = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      for (int i = 0; i < invalidCases; i++) {
        graph.invalid[Integer.parseInt(br.readLine().replaceAll("[^0-9]", ""))] = true;
      }

      graph.bfs(source);

      if (graph.parent[destination] == -1) {
        sb.append("-1\n");
      } else {
        sb.append(graph.findPath(source, destination) + "\n");
      }

      if (y != (cases-1)) {
        br.readLine();
      }
    }

    System.out.print(sb);
  }
}

Code: Select all

    private static int parseNumber(BufferedReader in) throws IOException {
        String row;
        while ((row = in.readLine()).trim().length() == 0);
        return Integer.parseInt(row.replaceAll(" ", ""), 10);
    }

Code: Select all

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;

class LockState implements Comparable<LockState>{
	String value;
	int hn=0;
	int gn=1;
	int fn=0;
	LockState prev=null;
	
	public LockState() {
		
	}
	
	public LockState(String value) {
		this.value=value;
	}
	
	@Override
	public String toString() {
		return this.value + " fn = "+this.fn;
	}

	public int compareTo(LockState s) {
		if(this.fn==s.fn) return 0;
		else if(this.fn>s.fn) return 1;
		else return -1;
	}
	
}

public class Main{
	
	static Vector<String> Visited = new Vector<String>();
	static String initCong = "";
	static String goalConf = "";
	public static void main(String[] args) {
	
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int nf ;
		
		
		for (int i = 0; i < n; i++) {
			String forbidden;
			Visited.clear();
			initCong="";
			goalConf="";
			if(i != 0) in.nextLine();
			for (int j = 0; j < 4; j++) {
				initCong+= String.valueOf(in.nextInt());
			}
			
			for (int j = 0; j < 4; j++) {
				goalConf+= String.valueOf(in.nextInt());
			}

			nf = in.nextInt();
			for (int j = 0; j < nf; j++) {
				forbidden="";
				for (int k = 0; k < 4; k++) {
					forbidden+= String.valueOf(in.nextInt());
				}
				Visited.add(forbidden);
			}
			
			if(i!=n-1){
				System.out.print(A_Star(new LockState(initCong)));
			}
			else {
				System.out.println(A_Star(new LockState(initCong)));
			}
		}

	}
	
	static int heuristic(String state){
		int g=0;
		for (int i = 0; i < state.length(); i++) {
			int xi= state.charAt(i) - 48;
			int xj= goalConf.charAt(i) - 48;
			if((xi<5 && xj>5) || (xi>5 && xj<5)){
				g+=(10-Math.abs(xi-xj))%10;
			}
			else g+=(Math.abs(xi-xj))%10;
		}
		
		return g;
	}
	

	
	static Vector<LockState> getNextStates(LockState state){
		Vector<LockState> neighbours = new Vector<LockState>();
		LockState next;
		for (int i = 0; i < state.value.length(); i++) {
			char[] tabchar = state.value.toCharArray();
			int charint = state.value.charAt(i)-48;
			if(charint==0){
				tabchar[i]='1';
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
				
				tabchar[i]='9';
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
			}
			else {
				tabchar[i]=(char)('0'+(charint+1)%10);
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
				
				tabchar[i]=(char)('0'+(charint-1)%10);
				next = new LockState(String.valueOf(tabchar));
				next.hn=heuristic(String.valueOf(tabchar));
				neighbours.add(next);
			}
		}

		return neighbours;
	}
	
	static int A_Star(LockState s0){
		PriorityQueue<LockState> prqueue = new PriorityQueue<LockState>();
		Vector<LockState> nexts;
		if(initCong.compareTo(goalConf)==0) return 0;
		if(Visited.contains(goalConf)) return -1;
		prqueue.add(s0);	
		while(!prqueue.isEmpty()){
			LockState test = prqueue.poll();
			if(test.value.equals(goalConf)){

				return test.gn-1;
			}
			
			Visited.add(test.value);
			
			nexts=getNextStates(test);
			
			for (int i = 0; i < nexts.size(); i++) {
				if(!Visited.contains(nexts.elementAt(i).value)){
					nexts.elementAt(i).prev=test;
					nexts.elementAt(i).gn+=test.gn;
					nexts.elementAt(i).fn=nexts.elementAt(i).gn+nexts.elementAt(i).hn;
					prqueue.add(nexts.elementAt(i));
				}
			}

		}
		return -1;
	}
	
}