Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Problem sa skakacem

[es] :: Java :: Problem sa skakacem

[ Pregleda: 2301 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
62.4.55.*



+2 Profil

icon Problem sa skakacem16.04.2016. u 18:18 - pre 96 meseci
Braćo pomažite.
Date su dva polja šahovskoj tabli, početno (npr. A1) i završno (npr. H6). Napisati metod skakac() koji treba
da učita početno i krajnje polje i odredi najmanji broj poteza koji je potreban skakaču da stigne sa početnog
polja na završno polje. (Napomena: zadatak se može riješiti primjenom reda).

Takav zadatak mi treba ne mogu ga na netu naci
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12846



+4783 Profil

icon Re: Problem sa skakacem16.04.2016. u 20:07 - pre 96 meseci
Pa, zadatak vec imas, upravo si ga napisao. Tako da se moze reci da je problem resen
 
Odgovor na temu

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
62.4.55.*



+2 Profil

icon Re: Problem sa skakacem16.04.2016. u 22:10 - pre 96 meseci
Znam ali mi treba src code ako ko ima ili barem nešto uradjeno
 
Odgovor na temu

Aleksandar Đokić

Član broj: 13478
Poruke: 4793
*.dynamic.sbb.rs.



+638 Profil

icon Re: Problem sa skakacem16.04.2016. u 23:07 - pre 96 meseci
A jel znas to matematicki i logicki da resis i da napravis algoritam? Pisanje koda posle se svodi na sintaksu.

U mrezama se to zove SPF, a koristi cini mi se algo koji se zove Dijkstra.
 
Odgovor na temu

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
62.4.55.*



+2 Profil

icon Re: Problem sa skakacem18.04.2016. u 00:24 - pre 96 meseci
Brate ja ga ne znam uraditi.Ako ko zna mogao bi postaviti src kode.Hvala unaprijed!
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem18.04.2016. u 00:41 - pre 96 meseci
Probaj ovo, nisam proveravao, a preuzeto sa: Stackoverflow.com

Code:

public class Horse {

    private int[][] board;
    private int[] xer = { 2, 1, -1, -2, -2, -1, 1, 2 };
    private int[] yer = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private final static int A_BIG_NUMBER = 10000;
    private final static int UPPER_BOUND = 64;


    public Horse() {
        board =  new int[8][8];
    }

    private int solution(int x, int y, int destx, int desty, int move) {

        if(move == UPPER_BOUND) {
            /* lets put an upper bound to avoid stack overflow */
            return A_BIG_NUMBER;
        }

        if(x == 6 && y ==5) {
            board[6][5] = 1;
            return 1;
        }
        int min = A_BIG_NUMBER;
        for (int i = 0 ; i < xer.length; i++) {
            if (isMoveGood(x + xer[i], y + yer[i])) {
                if(board[x + xer[i]][y + yer[i]] != 0) {
                    min = Integer.min(min, 1 + board[x +xer[i]] [y +yer[i]]);                   
                } else {
                    min = Integer.min(min, 1 + solution(x + xer[i], y + yer[i], destx, desty, move + 1));   
                }                   
            }
        }   
        board[x][y] = min;
        return min;
    }


    private boolean isMoveGood(int x, int y) {
        if (x >= 0 && x < board.length && y >= 0 && y < board.length)
            return true;
        return false;
    }


    public static void main(String[] args) {

        int destX = 6;
        int destY = 7;
        final Horse h = new Horse();
        System.out.println(h.solution(0, 0, destX, destY, 0));
    }
}

 
Odgovor na temu

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
*.crnagora.net.



+2 Profil

icon Re: Problem sa skakacem19.04.2016. u 21:11 - pre 96 meseci
Ne radi.
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem19.04.2016. u 21:57 - pre 96 meseci
Pa jesi li probao da vidis gde je problem !?
 
Odgovor na temu

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
62.4.55.*



+2 Profil

icon Re: Problem sa skakacem19.04.2016. u 23:22 - pre 96 meseci
Uopšte neće značu kucam polje 0,0 i 1,2 to bi trebalo jedan potez kaže 6 poteza.
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem19.04.2016. u 23:34 - pre 96 meseci
@ RasoRaso

Uzmi papir, olovku, šahovsku tablu i jednog skakača(srb. Konja)....


 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem19.04.2016. u 23:36 - pre 96 meseci
Ako je pozicija 0,0----donji levi ugao npr. ne možeš da postaviš poziciju 1,2....probaj sa 1,3

PS: nisam ni pogledao kako radi gorepostavljeni Alg. Ako ti je jako bitno ili za neko takmičenje može i na Skype...

PPS: Slučajno Imam integrisan LSM pa možemo i preko toga da probamo zajedno da rešimo prob!

[Ovu poruku je menjao galaksija dana 20.04.2016. u 00:47 GMT+1]
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem20.04.2016. u 01:44 - pre 96 meseci
Ok, teško pitanje zahteva odgovor:...do sada meni najteže ali rešeno !!!
 
Odgovor na temu

galaksija
Novi Sad

Član broj: 49290
Poruke: 82



+4 Profil

icon Re: Problem sa skakacem20.04.2016. u 01:50 - pre 96 meseci
Ovako:

Klasa "ChessCoordinate.java"

Code:

// ChessCoordinate provides an abstraction for valid chess position on a square chess board of square BOARD_SIZE
// Can be setup using algebraic chess notation
class ChessCoordinate 
{
    //Maps the integer horizontal co-ordinates to constant letter representations from algebra co-ordinates
    private enum AlgebraicXCoordinate {
        A(1), B(2), C(3), D(4), E(5), F(6), G(7), H(8);

        private int xCoordinate;

        //Map each enum value to an integer representing the x-coordinate
        private AlgebraicXCoordinate(final int coordinate)
        {
            this.xCoordinate = coordinate;
        }

        public int getValue()
        {
            return this.xCoordinate;
        }

        public static AlgebraicXCoordinate fromInt(int coordinate) 
        {
            for (AlgebraicXCoordinate algebraCoordinate : AlgebraicXCoordinate.values()) 
            {
                if (coordinate == algebraCoordinate.getValue()) 
                {
                    return algebraCoordinate;
                }
            }

            throw new IllegalArgumentException("Invalid position co-ordinate for algebraic chess notation.");
        }
    }

    public int x; //horizontal coordinate
    public int y; //vertical coordinate

    public static int BOARD_SIZE = 8; //size of one side of the square chessboard

    //Throws IllegalArgumentException if invalid co-ordinate range
    public ChessCoordinate(int xCoordinate, int yCoordinate) throws IllegalArgumentException
    {
        if (isValidCoordinate(xCoordinate,yCoordinate))
        {
            x = xCoordinate;
            y = yCoordinate;
        } else {
            throw new IllegalArgumentException("Invalid position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE);
        }
    }

    //Constructor for a position coordinate from algebraic chess notation (eg. A8 => x=1,y=8 , B2 => x=2,y=2 ...)
    //Throws IllegalArgumentException if an invalid algebraic chess notation is provided
    public ChessCoordinate(String algebraCoordinate) throws IllegalArgumentException
    {
        if (algebraCoordinate.length() == 2)
        {
            try {
                x = AlgebraicXCoordinate.valueOf(algebraCoordinate.substring(0,1).toUpperCase()).getValue(); //Use AlgebraicXCoordinate enum
            } catch (IllegalArgumentException e) {
                throw new IllegalArgumentException("Invalid horizontal algebraic co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE);
            }

            try {    
                y = Integer.parseInt(algebraCoordinate.substring(1));
            } catch (NumberFormatException e) {
                throw new IllegalArgumentException("Invalid vertical position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE);
            }

            if (!isValidCoordinate(x,y))
            {
                throw new IllegalArgumentException("Invalid algebraic position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE);
            }

        } else {
            throw new IllegalArgumentException("Invalid algebraic position co-ordinate. Board size is: " + BOARD_SIZE + " by " + BOARD_SIZE);
        }
    }

    //Is the coordinate a valid position on the defined board size
    public static boolean isValidCoordinate(int xCoordinate, int yCoordinate)
    {
        if (xCoordinate >= 1 && xCoordinate <= BOARD_SIZE && yCoordinate >= 1 && yCoordinate <= BOARD_SIZE)
        {
            return true;
        } else {
            return false;
        }
    }

    //When does one ChessCoordinate equal another ChessCoordinate
    //Required method to override for use with 'contains' in collections
    //
    //Returns boolean
    public boolean equals(Object other)
    {
        ChessCoordinate another = (ChessCoordinate)other;

        if (another.x == this.x && another.y == this.y)
        {
            return true;
        } else {
            return false;
        }
    }

    //Allows for storage of class in Hash based collections
    //Builds a unique int as the hashcode based on concatenating the string representation of each part of the coordinate
    //
    //Returns int that is unique for each ChessCoordinate
    public int hashCode()
    {
        String xString = String.valueOf(this.x);
        String yString = String.valueOf(this.y);
        String stringCoordinate = xString + yString;
        return Integer.parseInt(stringCoordinate);
    }

    //Return the algebraic notation of the object's chess co-ordinate
    public String toString()
    {
        String xCoordinate = AlgebraicXCoordinate.fromInt(this.x).name();
        String yCoordinate = String.valueOf(this.y);
        return (xCoordinate + yCoordinate);
    }

}


#################################################

Klasa "ChessPiece.java"

Code:

import java.util.*;

public abstract class ChessPiece {

    //Given a starting position what are the valid co-ordinates a chess piece can move to next
    //
    //Assumes empty chess board with no other pieces
    //
    //Returns ArrayList of valid ChessCoordinates for next move of a chess piece
    public abstract ArrayList<ChessCoordinate> validMoves(ChessCoordinate startPosition);

}


##################################################

Klasa "ChessShortestPath.java"

Code:

import java.util.*;

//ChessShortestPath provides a solution to the shortest path between a starting position and end position for a knight chess piece
class ChessShortestPath {
    
    public ChessCoordinate startPos;
    public ChessCoordinate endPos;
    public ChessPiece pieceType;

    public ChessShortestPath(ChessCoordinate start, ChessCoordinate end, ChessPiece piece)
    {
        startPos = start;
        endPos = end;
        pieceType = piece;
    }

    //Finds the shortest path between a start node and end node for a unweighted graph using Breadth First Search 
    //
    //For Chess Shortest Path, the chess board is an unweighted graph where the current position of the knight is the visited node in Breadth First Search and the positions of the possible next moves are the adjacent nodes
    //
    //Prints out the shortest path in terms of the steps of the shortest path, excluding the starting position
    public void shortestPath()
    {
        //Keep track of visited nodes and the parents of visited nodes (for finding the shortest path)
        HashMap<ChessCoordinate, ChessCoordinate> parentNode = new HashMap<ChessCoordinate, ChessCoordinate>();

        //Queue of nodes to visit 
        Queue<ChessCoordinate> positionQueue = new LinkedList<ChessCoordinate>();

        //intially add the starting node
        parentNode.put(startPos,null);
        positionQueue.add(startPos);

        //Breadth first search
        while (positionQueue.peek() != null) //check if anymore nodes to visit
        {
            ChessCoordinate currentPosition = positionQueue.poll();

            if (currentPosition.equals(endPos))
            {
                break; //we have reached the end position on the graph via the shortest path so stop searching
            }

            //otherwise get adjacent nodes (possible moves from current position for knight)
            ArrayList<ChessCoordinate> nextPositions = pieceType.validMoves(currentPosition);
            for (ChessCoordinate adjacentPosition : nextPositions)
            {
                //if this adjacent nodes is one that hasn't been visited add it to the queue
                //also keep track of the adjacent node's parent (the current node)
                if (!parentNode.containsKey(adjacentPosition))
                {
                    parentNode.put(adjacentPosition,currentPosition);
                    positionQueue.add(adjacentPosition);
                }
            }
        }

        //traverse back from end position coordinate to start position using the parent map to get shortest path
        //build up string of shortest path at same time
        ChessCoordinate currentNode = endPos; //start at the end node
        String shortestPath = "";
        while (parentNode.get(currentNode) != null) //stop once we are at the start node
        {
            shortestPath = currentNode.toString() + " " + shortestPath;
            currentNode = parentNode.get(currentNode);
        }

        if (shortestPath.length() == 0) //When start position = end position
        {
            shortestPath = startPos.toString();
        }

        //Print out the shortest path found, excluding start position and including end position
        System.out.println(shortestPath);
    }

    public static void main(String[] args)
    {


            try {
                //must catch checked exception for invalid co-ordinates arguments
                ChessShortestPath knightShortestPath = new ChessShortestPath(new ChessCoordinate("B1"), new ChessCoordinate("C5"), new Knight());
                knightShortestPath.shortestPath();
            } catch (IllegalArgumentException e) {
                System.out.println(e.getMessage());
            }

    }

}


##############################################################

Klasa "Knight.java"

Code:

import java.util.*;

class Knight extends ChessPiece {

    public ArrayList<ChessCoordinate> validMoves(ChessCoordinate startPosition)
    {
        //Will build up list of valid co-ordinates for next move
        ArrayList<ChessCoordinate> validCoordiantes = new ArrayList<ChessCoordinate>();

        int[] moves = {-2, -1, 1, 2};

        for (int xMove : moves) {
            for (int yMove : moves) {
                if (Math.abs(xMove) != Math.abs(yMove)) { //A Knight can only move 1 space in one direction and 2 in the other
                    if (ChessCoordinate.isValidCoordinate(startPosition.x + xMove, startPosition.y + yMove))
                    {
                        validCoordiantes.add((new ChessCoordinate((startPosition.x + xMove),(startPosition.y + yMove))));
                    }
                }
            }
        }

        return validCoordiantes;
    }

}



Klasa "ChessShortestPath" je main klasa i kada budes proveravao samo menjaj: "
Code:
ChessShortestPath knightShortestPath = new ChessShortestPath(new ChessCoordinate("B1"), new ChessCoordinate("C5"), new Knight());
"
 
Odgovor na temu

RasoRaso
Podgorica,Crna Gora

Član broj: 328876
Poruke: 34
62.4.55.*



+2 Profil

icon Re: Problem sa skakacem20.04.2016. u 09:35 - pre 96 meseci
Stvarno ti fala
 
Odgovor na temu

[es] :: Java :: Problem sa skakacem

[ Pregleda: 2301 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.