Diskuze: Cesta koně po šachovnici

Neaktivní uživatel

Člen

Neaktivní uživatel:13.9.2021 2:32

Ahoj, mám tento program pro nalezení nejrychlejší cesty koněm po šachovnici z bodu A do bodu B.
Potřebovala bych poradit s tím, jak vypsat nejen počet tahů, ale i souřadnice daných tahů (tedy vypsat cestu).
Děkuji

#include <iostream>
#include <set> //kontejner
#include <queue> //fronty
#include <climits> //konstanta
using namespace std;

// Mozne tahy konem
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 }; //rada
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 }; //sloupec

// Kontrola, že jsou pole na sachovnici, bool ma pouze dve moznosti
bool isValid(int x, int y, int N) {
    return (x >= 0 && x < N) && (y >= 0 && y < N);
}

struct Node //struct obsahuje ruzne promenne
{
    // (x, y) jsou souradnice
    // `dist` jak vzdalene pole minimalne je
    int x, y, dist;

    // konstrukce
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}

    bool operator<(const Node& o) const { //mapa porovna dva Node objekty, prvne x pote y
        return x < o.x || (x == o.x && y < o.y);
    }
};

// Najdi nejkratsi mozny pocet skoku od zacatku do konce
int najdiNejkratsiCestu(int N, Node src, Node dest)
{
    // Zkontroluje, jestli bylo pole navštívené
    set<Node> visited;

    // vytvor radu
    queue<Node> q;
    q.push(src);

    // smycka dokud to jde
    while (!q.empty())
    {
        Node node = q.front();
        q.pop();

        int x = node.x;
        int y = node.y;
        int dist = node.dist;

        // Pokud kun dosahne finalnich souradnic, vrat vzdalenost
        if (x == dest.x && y == dest.y) {
            return dist;
        }

        // Pokud bylo pole navštívené, preskoc
        if (!visited.count(node))
        {
            // Oznac pole za navstivene
            visited.insert(node);

            // Zkontroluj všech 8 moznych skoku a uloz spravne
            for (int i = 0; i < 8; i++)
            {
                // Ziskej novou pozici kone a pridej +1 ke vzdalenosti
                int x1 = x + row[i];
                int y1 = y + col[i];

                if (isValid(x1, y1, N)) {
                    q.push({ x1, y1, dist + 1 });
                }
            }

        }
    }

    // pokud tah nejde udelat, vrat nekonecno
    return INT_MAX;
}

int main()
{
    // N x N
    int N = 8;
    // souradnice vyjezdu
    int b;
    int d;
    cout << "Zadej sloupec vyjezdu: ";
    cin >> b;
    cout << "Zadej radu vyjezdu: ";
    cin >> d;
    Node src = { b, d };

    // souradnice dojezdu
    int e;
    int f;
    cout << "Zadej sloupec dojezdu: ";
    cin >> e;
    cout << "Zadej radu dojezdu: ";
    cin >> f;
    Node dest = { e, f };

    cout << "Nejkratsi cesta ma tahu: " <<
        najdiNejkratsiCestu(N, src, dest);

    return 0;
}

Zkusil jsem: Zkoušela jsem přidat cout do výsledku, ale to mi po chvíli došlo, že nestačí...

Chci docílit: Hledám způsob, jak vypsat dané tahy, nejen jejich počet.

Odpovědět

13.9.2021 2:32

Neaktivní uživatelský účet

Peter Mlich

Člen

Peter Mlich:13.9.2021 8:23

if (isValid(x1, y1, N)) {
    q.push({ x1, y1, dist + 1 });
}

Jestli to spravne chapu, tak to mas v tom q. jen tam musis pridat jeste predchozi souradnice nebo cislo predchoziho kroku, abys to mohla dohledat.

https://mlich.zam.slu.cz/js-ff/ff4b.htm
Ja tam vyuzivam seznam vsech nejkratsich cest. Hra pak nevypada tak fadne, predvidatelne, kudy to pobezi. Mam tam

List1: id-radku + id policka + seznam vsech moznych tahu z policka (cisla policek, kam se da) (pro jednoduchos dodrzuji smer) (id-radku a id policka muze byt totez, zalezi na tvem reseni)
List2: cyklus, ktery vytvari seznam cest, kde mam id-radku. Vyrazuji moznosti, ktere uz v seznamu jsou, aby mi nepridal smer tam-a-zpet jako novou trasu.
List3: Kdyz natrefim na policko B, tak zacnu cyklus pro list2 ukoncovat a zacnu zapisovat seznam cest, prvnich polozek. Ktery pak doplnim o ostatni policka podle list2.

List 1 tam bud vlozis rucne, nebo generujes z herni plochy. Ty mas problem trochu jiny, kun na sachovnici, ale v zasade muzes delat totez.
Ty List1 obchazis tim, ze kontrolijes u q (isValid(x1, y1, N)). Zjistis, ze tah ne mozne provest. Ale nemas v nem nic o predchozim kroku x,y. A neresis to, ze kun muze skocit tam a zase zpet.
Ja ten seznam prave nechavam ulozeny, protoze v nem hledam opakovane. Ty hledas jen jednou, tak to asi neni treba. Ale, nemas teda nic o predchozim kroku, radku, podle ktereho prochazis vsechny moznosti.

Nahoru Odpovědět

13.9.2021 8:23

Neaktivní uživatel

Člen

Neaktivní uživatel:13.9.2021 8:33

Děkuji, asi chápu, co tím chceš říct... bohužel je toto můj první program, a tak si úplně nejsem jistá, jak to udělat.

Nahoru Odpovědět

13.9.2021 8:33

Neaktivní uživatelský účet

DarkCoder

Člen

DarkCoder:13.9.2021 15:50

Jak už zde bylo napsáno, abys mohla vypsat úplnou cestu šachového jezdce, je třeba znát pozici pole ze kterého se jezdec na tuto pozici dostal. Jedním ze způsobů je, že každé pole je definováno souřadnicemi a indexem. Index představuje pozici předchozího pole ve frontě. Pro získání nových pozic kontrolujeme validitu, visitibilitu a pokud tento test projde, zapíšeme do fronty nové pole jehož index bude roven pozici pole ve frontě, ze kterého jsme se na tuto pozici dostali. Jakmile se dostaneme do cíle, lze pomocí indexu přečíst souřadnici předchozího pole. Čtení provádíme tak dlouho, dokud nepřečteme souřadnice na nultém indexu (startovní pozice). V průběhu zjišťování cesty si započítáváme počet kroků, což odpovídá počtu tahů od začátku do konce. Jednotlivé souřadnice si zapisujeme do nového pole, které pro výpis cesty od začátku do konce je třeba číst odzadu.

Nahoru Odpovědět

13.9.2021 15:50

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Peter Mlich

Člen

Peter Mlich:14.9.2021 8:38

Z toho trasu neziskas, mas tam vsechny moznosti. Potrebujes vedet, ke kteremu radku se to vztahuje.
Potrebujes napsat uplne jiny program, ktery, krome toho, ze urci vzdalenost, dokaze ukladat i trasu.
To tvuj program nikdy jen s malou upravou delat nemuze.

 Trasa z bodu A do bodu B (policko 13)
[ predchozi-radek, from, to ]
0: [-1. A, 1]
1: [-1. A, 2]
2: [-1. A, 3]
3: [-1. A, 4]
4: [-1. A, 5]
5: [-1. A, 6]
6: [-1. A, 7]
7: [-1. A, 8]...
8: [5. 6, 13] (radek 5: [-1. A, 6]...)
9: [A, 6, 14]...

13 je konec, rekneme (bod B)
je to kombinace radek 8: [5. 6, 13] ( [ predchozi-radek=5, from=6, to=13 ] )
Takze ted si muzes trasu zpetne dohledat. V seznamu staci najit prislusna cisla predchozich radku
8: [5. 6, 13] -> radek 5
5: [-1. A, 6] -> radek -1, vychozi policko
Trasa je 13 - 6 - A nebo obracene  A - 6 - 13

Editováno 14.9.2021 8:40

Nahoru Odpovědět

14.9.2021 8:38

Peter Mlich

Člen

Peter Mlich:14.9.2021 8:42

Jo, policka zapisuje jako 1 az 64. Ty jako x,y, ale to je jen drobny detail, na kterem nesejde. x,y je stejne dobre.
1,2,3,4,5,6,7,8 je jen priklad. Na sachovnici to budou jina cisla pro tah kone. To resi ten tvuj cyklus a isValid, to je ok.

Editováno 14.9.2021 8:44

Nahoru Odpovědět

14.9.2021 8:42

DarkCoder

Člen

DarkCoder:19.9.2021 15:51

Zde se můžeš inspirovat, jak vypsat cestu jezdce spolu s nejkratším počtem tahů. Psáno v C.

#include <stdio.h>

#define N 8
#define M 8

struct Node {
        char x, y;
        struct Node *prev;
};

int row[M] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[M] = { -1, 1, 1, -1, 2, -2, 2, -2 };

void push(struct Node* queue, struct Node* node, unsigned char *pos, unsigned char (*dim)[N]);

int main(void) {
        struct Node list[N * N] = { 0 };
        unsigned char pos = 0, n = 0;
        unsigned char visit[N][N] = { 0 };
        struct Node start = { 0, 0, NULL };
        struct Node end = { 1, 1, NULL };
        struct Node tmp = start, *ptmp = &tmp;
        struct Node path[N * N] = { 0 };
        unsigned char steps = 0;

        push(list, &start, &n, visit);

        while (!((tmp.x == end.x) && (tmp.y == end.y))) {
                for (int i = 0; i < M; i++) {
                        if (list[pos].x + col[i] >= 0 && list[pos].x + col[i] < N && list[pos].y + row[i] >= 0 && list[pos].y + row[i] < N) {
                                if (!visit[list[pos].x + col[i]][list[pos].y + row[i]]) {
                                        tmp.x = list[pos].x + col[i];
                                        tmp.y = list[pos].y + row[i];
                                        tmp.prev = list + pos;
                                        push(list, &tmp, &n, visit);
                                        if ((tmp.x == end.x) && (tmp.y == end.y)) break;
                                }
                        }
                }
                pos++;
        }

        do {
                path[steps].x = ptmp->x;
                path[steps].y = ptmp->y;
                ptmp = ptmp->prev;
                steps++;

        } while (ptmp);
        steps--;

        printf("Cesta jezdce od [%d %d] do [%d %d]\n", start.x, start.y, end.x, end.y);
        for(int i = steps; i>=0; i--) printf("[%d %d] ", path[i].x, path[i].y);
        printf("- Pocet tahu: %d\n", steps);

        return 0;
}

void push(struct Node *list, struct Node* node, unsigned char *pos, unsigned char(*dim)[N]) {
        (list + *pos)->x = node->x;
        (list + *pos)->y = node->y;
        (list + *pos)->prev = node->prev;
        (*pos)++;
        dim[node->x][node->y] = 1;
}

Nahoru Odpovědět

19.9.2021 15:51

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Peter Mlich

Člen

Peter Mlich:20.9.2021 10:13

Kdyz tam mas ty ukazatele, mozna by slo na predchozi krok jit primo pres ukazatel pole, pro 'prev'. Coz by bylo o 100% lepsi nez pouzivam ja, cisla radku. Ale nevim, zda to v c jde a jak to zapsat. list + pos je ale nejspis stejne dobre.

tmp.prev = list + pos;
tmp.prev = list[pos];

Nahoru Odpovědět

20.9.2021 10:13

DarkCoder

Člen

DarkCoder:20.9.2021 11:20

Však to tak je, k předchozímu poli je přistupováno pomocí ukazatele. Od toho je definován ukazatel prev na strukturu uvnitř struktury Node.

struct Node {
        char x, y;
        struct Node *prev; // ukazatel na předchozí pole
};

Pří ukončení while cyklu obsahuje strukturová proměnná tmp souřadnice cílového pole a ukazatel na pole, ze kterého jsme se na toto pole dostali. Toho je využito v následujícím cyklu do-while, kde právě pomocí ukazatelů na předchozí prvek se dostaneme počáteční pole. Do nového pole jsou pak zapisovány souřadnice přímo pomocí ukazatele.

do {
        path[steps].x = ptmp->x;
        path[steps].y = ptmp->y;
        ptmp = ptmp->prev;
        steps++;
} while (ptmp);
steps--;

Jelikož si cestou k cíli nepoznamenávám počet kroků, představuje postupný zápis souřadnic do pole cestu v obráceném pořadí. Elegantnější by bylo použít obousměrný seznam, kdy cestou zpět by se uchovávala informace o následujícím poli.

struct Node {
        char x, y;
        struct Node *prev;
        struct Node *next;
};

Pak by se nemuselo používat pole pro cestu path, ale využil by se již seznam polí pro tahy jezdce list. Jelikož je ale získání cesty přímočaré a stejně tak efektivní i jeho výpis, nebyl obousměrný seznam použit. Ač to zde není důležité, lze díky seznamu přistupovat přímo k jednotlivým částem cesty na rozdíl od obousměrného seznamu, kde bychom museli procházet seznam přes ukazatele.

K tomuto:

tmp.prev = list + pos;
tmp.prev = list[pos];

První příkaz je správný, Výsledkem výrazu list + pos je ukazatel. K ukazateli je možné přičítat celočíselnou hodnotu.
Druhý příkaz je chybný. Pravá strana není ukazatel ale prvek struktury.

Pokud bychom chtěli ukazateli přiřadit adresu prvku pole struktur, vypadalo by to následovně:

tmp.prev = &list[pos];
tmp.prev = list + pos;
ptmp->prev = &list[pos];
ptmp->prev = list + pos;

Nahoru Odpovědět

20.9.2021 11:20

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Nejčastěji vyhledáváné

Diskuze: Cesta koně po šachovnici