Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Hashtable;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.NoSuchElementException;
- import java.util.Scanner;
- import java.util.Stack;
- import java.util.Iterator;
- class SLLNode<E> {
- protected E element;
- protected SLLNode<E> succ;
- public SLLNode(E elem, SLLNode<E> succ) {
- this.element = elem;
- this.succ = succ;
- }
- @Override
- public String toString() {
- return element.toString();
- }
- }
- interface Queue<E> {
- // Elementi na redicata se objekti od proizvolen tip.
- // Metodi za pristap:
- public boolean isEmpty ();
- // Vrakja true ako i samo ako redicata e prazena.
- public int size ();
- // Ja vrakja dolzinata na redicata.
- public E peek ();
- // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
- // Metodi za transformacija:
- public void clear ();
- // Ja prazni redicata.
- public void enqueue (E x);
- // Go dodava x na kraj od redicata.
- public E dequeue ();
- // Go otstranuva i vrakja pochetniot element na redicata.
- }
- class LinkedQueue<E> implements Queue<E> {
- // Redicata e pretstavena na sledniot nacin:
- // length go sodrzi brojot na elementi.
- // Elementite se zachuvuvaat vo jazli dod SLL
- // front i rear se linkovi do prviot i posledniot jazel soodvetno.
- SLLNode<E> front, rear;
- int length;
- // Konstruktor ...
- public LinkedQueue () {
- clear();
- }
- public boolean isEmpty () {
- // Vrakja true ako i samo ako redicata e prazena.
- return (length == 0);
- }
- public int size () {
- // Ja vrakja dolzinata na redicata.
- return length;
- }
- public E peek () {
- // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
- if (front == null)
- throw new NoSuchElementException();
- return front.element;
- }
- public void clear () {
- // Ja prazni redicata.
- front = rear = null;
- length = 0;
- }
- public void enqueue (E x) {
- // Go dodava x na kraj od redicata.
- SLLNode<E> latest = new SLLNode<E>(x, null);
- if (rear != null) {
- rear.succ = latest;
- rear = latest;
- } else
- front = rear = latest;
- length++;
- }
- public E dequeue () {
- // Go otstranuva i vrakja pochetniot element na redicata.
- if (front != null) {
- E frontmost = front.element;
- front = front.succ;
- if (front == null) rear = null;
- length--;
- return frontmost;
- } else
- throw new NoSuchElementException();
- }
- }
- class Graph<E> {
- int num_nodes; // broj na jazli
- E nodes[]; // informacija vo jazlite - moze i ne mora?
- int adjMat[][]; // matrica na sosednost
- @SuppressWarnings("unchecked")
- public Graph(int num_nodes) {
- this.num_nodes = num_nodes;
- nodes = (E[]) new Object[num_nodes];
- adjMat = new int[num_nodes][num_nodes];
- for(int i=0;i<this.num_nodes;i++)
- for(int j=0;j<this.num_nodes;j++)
- adjMat[i][j]=0;
- }
- public Graph(int num_nodes, E[] nodes) {
- this.num_nodes = num_nodes;
- this.nodes = nodes;
- adjMat = new int[num_nodes][num_nodes];
- for(int i=0;i<this.num_nodes;i++)
- for(int j=0;j<this.num_nodes;j++)
- adjMat[i][j]=0;
- }
- int adjacent(int x,int y)
- { // proveruva dali ima vrska od jazelot so indeks x do jazelot so indeks y
- return (adjMat[x][y]!=0)?1:0;
- }
- void addEdge(int x,int y)
- { // dodava vrska megu jazlite so indeksi x i y
- adjMat[x][y]=1;
- }
- void deleteEdge(int x,int y)
- {
- // ja brise vrskata megu jazlite so indeksi x i y
- adjMat[x][y]=0;
- }
- // Moze i ne mora?
- E get_node_value(int x)
- { // ja vraka informacijata vo jazelot so indeks x
- return nodes[x];
- }
- // Moze i ne mora?
- void set_node_value(int x, E a)
- { // ja postavuva informacijata vo jazelot so indeks na a
- nodes[x]=a;
- }
- public int getNum_nodes() {
- return num_nodes;
- }
- public void setNum_nodes(int num_nodes) {
- this.num_nodes = num_nodes;
- }
- void dfsSearch(int node) {
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- dfsRecursive(node, visited);
- }
- void dfsRecursive(int node, boolean visited[]) {
- visited[node] = true;
- System.out.println(node + ": " + nodes[node]);
- for (int i = 0; i < this.num_nodes; i++) {
- if(adjacent(node, i)==1){
- if (!visited[i])
- dfsRecursive(i, visited);
- }
- }
- }
- void dfsNonrecursive(int node) {
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- visited[node] = true;
- System.out.println(node + ": " + nodes[node]);
- Stack<Integer> s = new Stack<Integer>();
- s.push(node);
- int pom;
- while (!s.isEmpty()) {
- pom = s.peek();
- int pom1 = pom;
- for (int i = 0; i < num_nodes; i++) {
- if(adjacent(pom,i)==1){
- pom1 = i;
- if(!visited[i])
- break;
- }
- }
- if(!visited[pom1]){
- visited[pom1] = true;
- System.out.println(pom1 + ": " + nodes[pom1]);
- s.push(pom1);
- }
- else
- s.pop();
- }
- }
- void bfs(int node, int end){
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- visited[node] = true;
- //System.out.println(node+": " + nodes[node]);
- Queue<Integer> q = new LinkedQueue<Integer>();
- q.enqueue(node);
- int pom;
- while(!q.isEmpty()){
- pom = q.dequeue();
- for (int i = 0; i < num_nodes; i++) {
- if(adjacent(pom, i)==1){
- if (!visited[i]){
- visited[i] = true;
- System.out.println(i+": " + nodes[i]);
- q.enqueue(i);
- }
- }
- }if(pom == end) break;
- }
- }
- @Override
- public String toString() {
- String ret=" ";
- for(int i=0;i<num_nodes;i++)
- ret+=nodes[i]+" ";
- ret+="\n";
- for(int i=0;i<num_nodes;i++){
- ret+=nodes[i]+" ";
- for(int j=0;j<num_nodes;j++)
- ret+=adjMat[i][j]+" ";
- ret+="\n";
- }
- return ret;
- }
- }
- public class Robot {
- Graph g;
- int start_node; //indeks temeto koe e vlez
- int end_node; //indeks na temeto koe e izlez
- int m;
- int n;
- int x1,y1,x2,y2;
- Hashtable<String,Integer> h;
- Hashtable<Integer,String> dh;
- public Robot() {
- h = new Hashtable<String,Integer>();
- dh = new Hashtable<Integer, String>();
- }
- /*
- void bfs(int node, int end){
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- visited[node] = true;
- //System.out.println(node+": " + nodes[node]);
- Queue<Integer> q = new LinkedQueue<Integer>();
- q.enqueue(node);
- int pom;
- while(!q.isEmpty()){
- pom = q.dequeue();
- for (int i = 0; i < num_nodes; i++) {
- if(adjacent(pom, i)==1){
- if (!visited[i]){
- visited[i] = true;
- System.out.println(i+": " + nodes[i]);
- q.enqueue(i);
- }
- }
- }if(pom == end) break;
- }
- }*/
- int bfs(Pair start, int endx,int endy)
- {
- boolean visited[] = new boolean[g.num_nodes];
- for (int i = 0; i < g.num_nodes; i++)
- visited[i] = false;
- boolean temp = false;
- for(int i=0; i<g.num_nodes; i++)
- {
- //System.out.println(dh.get(i) +" " + start.x + "," + start.y);
- if(dh.get(i).equals( start.x + "," + start.y))
- {
- temp =true;
- break;
- }
- }
- if(!temp)
- return -1;
- visited[h.get(start.x + "," + start.y)] = true;
- Queue<Pair> q = new LinkedQueue<>();
- q.enqueue(start);
- while(!q.isEmpty())
- {
- Pair pom = q.dequeue();
- if(pom.x==endx && pom.y == endy)
- {
- return pom.len;
- }
- for(int i=0; i<g.num_nodes; i++)
- {
- if(g.adjacent(h.get(pom.x + "," + pom.y), i)==1)
- {
- if(!visited[i])
- {
- visited[i]=true;
- String [] s= dh.get(i).split(",");
- int x = Integer.parseInt(s[0]);
- int y = Integer.parseInt(s[1]);
- q.enqueue(new Pair(x,y,pom.len+1));
- }
- }
- }
- }
- return -1;
- }
- public void generateGraph(int rows, int columns, String[] in){
- int num_nodes = 0;
- int pom = 0;
- String key;
- ArrayList<String> arrKey = new ArrayList<>();
- for(int i=0; i<rows; i++){
- for(int j=0; j<columns; j++){
- if(in[i].charAt(j)!='1'){
- key = i+","+j;
- arrKey.add(key);
- h.put(key, num_nodes);
- dh.put(num_nodes, key);
- if(i==x1 && j==y1)
- start_node = num_nodes;
- if(i==x2 && j==y2)
- end_node = num_nodes;
- num_nodes++;
- }
- }
- }
- g = new Graph(num_nodes, arrKey.toArray());
- int x;
- int y;
- //generiranje na matrica na sosednost
- //System.out.println(in[0].charAt(1));
- //System.out.println("Vlegov");
- for(int i=0; i<rows-1; i++){
- for(int j=0; j<columns-1; j++){
- if(in[i].charAt(j)!='1'
- && in[i+1].charAt(j+1)!='1'
- && in[i].charAt(j+1)!='1'
- && in[i+1].charAt(j)!='1'){
- //dali ima teme desno od nego
- if(i<rows-1 && j<columns-2 && in[i].charAt(j+2)!='1'
- && in[i+1].charAt(j+2)!='1')
- {
- x = h.get(i+ "," +j);
- //System.out.println(j);
- y = h.get(i+ "," +(j+1));
- g.addEdge(x, y);
- }
- //dali ima teme levo od nego
- if(j>=1 && in[i].charAt(j-1)!='1' && in[i+1].charAt(j-1)!='1' && i<rows-1){
- x = h.get(i+","+j);
- y = h.get(i+","+(j-1));
- g.addEdge(x, y);
- }
- //dali ima teme nad nego
- if(i>=1 && in[i-1].charAt(j)!='1' && in[i-1].charAt(j+1)!='1' && j<columns-1){
- x = h.get(i+","+j);
- y = h.get((i-1)+","+j);
- g.addEdge(x, y);
- }
- //dali ima teme pod nego
- if(i<rows-2 &&
- in[i+2].charAt(j)!='1'
- && in[i+2].charAt(j+1)!='1' && j<columns-1){
- x = h.get(i+","+j);
- y = h.get((i+1)+","+j);
- g.addEdge(x, y);
- }
- }
- }
- }
- }
- void findPath(){
- boolean visited[] = new boolean[g.getNum_nodes()];
- for (int i = 0; i < g.getNum_nodes(); i++)
- visited[i] = false;
- visited[start_node] = true;
- Stack<Integer> s = new Stack<Integer>();
- s.push(start_node);
- int pom;
- while (!s.isEmpty() && s.peek()!=end_node) {
- pom = s.peek();
- int pom1 = pom;
- for (int i = 0; i < g.getNum_nodes(); i++) {
- if(g.adjacent(pom,i)==1){
- pom1 = i;
- if(!visited[i])
- break;
- }
- }
- if(!visited[pom1]){
- visited[pom1] = true;
- //System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
- s.push(pom1);
- }
- else
- s.pop();
- }
- if(s.isEmpty())
- System.out.println("Nema reshenie");
- else{
- Stack<Integer> os = new Stack<Integer>();
- while(!s.isEmpty())
- os.push(s.pop());
- while(!os.isEmpty())
- System.out.println(os.pop());
- }
- // public int findPath(){
- // boolean visited[] = new boolean[g.getNum_nodes()];
- // for (int i = 0; i < g.getNum_nodes(); i++)
- // visited[i] = false;
- // visited[start_node] = true;
- // Stack<Integer> s = new Stack<Integer>();
- // s.push(start_node);
- //
- // int pom;
- // while (!s.isEmpty() && s.peek()!=end_node) {
- // pom = s.peek();
- // int pom1 = pom;
- // for (int i = 0; i < g.getNum_nodes(); i++) {
- // if(g.adjacent(pom,i)==1){
- // pom1 = i;
- // if(!visited[i])
- // break;
- // }
- // }
- // if(!visited[pom1]){
- // visited[pom1] = true;
- // //System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
- // s.push(pom1);
- // }
- // else
- // s.pop();
- // }
- // if(s.isEmpty())
- // {System.out.println("Nema kraj");
- // return -1;
- // }
- // else{
- // Stack<Integer> os = new Stack<Integer>();
- // while(!s.isEmpty())
- // {
- // os.push(s.pop());
- // System.out.print(os.peek()+ " ");
- // }
- // return os.size();
- // }
- }
- // String findPath(int v, int w) {
- // Queue<Integer> q = new LinkedQueue<Integer>();
- // boolean[] visited = new boolean[g.num_nodes];
- // String[] pathTo = new String[g.num_nodes];
- //
- // q.enqueue(v);
- // pathTo[v] = v+" ";
- // while(q.peek() != null) {
- // if(runBFS(q.dequeue(),w,visited,q,pathTo))
- // break;
- // }
- // return pathTo[w];
- // }
- //
- // private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
- // if(visited[v]) {
- // }
- // else if(v == w){
- // return true;
- // }
- // else {
- // visited[v] = true;
- // Iterator vi = g.(v);
- // while(vi.hasNext()) {
- // int nextVertex = vi.next();
- // pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
- // q.enqueue(nextVertex);
- // }
- // }
- // return false;
- // }
- //
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- Robot r = new Robot();
- int m = in.nextInt();
- int n = in.nextInt();
- in.nextLine();
- //in.nextLine();
- String[] line = new String[m];
- for(int i=0; i<m; i++)
- {
- line[i] = in.nextLine();
- line[i] = line[i].replaceAll("\\s", "");
- //in.nextLine();
- }
- //System.out.println(line[6]);
- int x1,y1,x2,y2;
- x1 = in.nextInt();
- y1 = in.nextInt();
- x2 = in.nextInt();
- y2 = in.nextInt();
- in.close();
- Pair p = new Pair(x1-1,y1-1,0);
- r.generateGraph(m, n, line);
- System.out.println(r.bfs(p, x2-1, y2-1));
- //r.g.bfs(r.h.get((x1-1)+","+(y1-1)));
- }
- }
- class Pair
- {
- int x,y, len;
- Pair(int i,int j, int len)
- {
- this.x = i;
- this.y = j;
- this.len = len;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement