Witajcie!
Przybywam z problemem algorytmicznym, co w związku z działem pewnie nie dziwi :).
Problem brzmi następująco: mamy tablicę kwadratową, na której znajdują się "miny" i mam znaleźć pole, które jest "wyjściem". Szczegół taki, że nie wiadomo, które pole jest wyjściem i nieznana jest też liczba, ani rozmieszczenie min. Dostajemy tylko liczę min znajdującą się w pobliżu naszego "zwiedzonego" pola. Mamy do dyspozycji nieznaną liczbę pomyłek (wiadomo, że l. min> l. prób), więc brtueforce raczej odpada ;). Pole wyjściowe może być otoczone minami, a przy każdej kolejnej próbie mamy do dyspozycji "mapę" zwiedzonych już pól.
Na tę chwilę mój pomysł polegał na tym, żeby odwiedzić wszystkie pola, które wiemy, że są wolne od min i zaznaczać je w tablicy, a samo przeszukiwanie zaimplementować jako BFS. Problem taki, że w przypadku, gdy pole jest otoczone minami to algorytm pola wyjścia nie znajdzie. Nie wiem też za bardzo co zrobić w sytuacji, gdzie min w pobliżu jest na przykład 4-6, bo wtedy można tylko "strzelać", na którym polu nie ma żadnej miny. Jeden z pomysłów to też rozwiązywanie tego podobnie do tych kolorowanek, gdzie na krawędzi są liczby i musimy pokolorować daną liczę pól, tylko tyle, że nie znam żadnego takiego algorytmu, a implementowanie AI to nie jest najlepszy pomysł ;).
@Rev ostatnio rozklepywał nonogram na ctfie, moze ci coś pomoże ;)
https://github.com/p4-team/ctf/tree/master/2015-12-05-seccon/qr_nonogram_300
Czym jest „próba”? Co to jest „mapa zwiedzonych pól” i jak się ona zmienia? Czy jest to po prostu problem rozwiązania windowsowego sapera?
To doprecyzowując: może zdarzyć się sytuacja, że "wejdziemy" w minę, ona wtedy wybuchnie, jednak mamy do dyspozycji jakąś nieznaną liczbę pomyłek i ta liczba pomyłek to próba. W warunkach zadania jest też, że można korzystać z poprzednich wyników przeszukiwania - tzn. wchodząc w minę ona wybucha i to pole mamy "czyste", więc wiemy, że możemy przez nie przejść dalej, to nazwałem "mapą zwiedzonych pól".
Ech, ciągle zbyt mało konkretnie. Czy na starcie mam odkryte jakiekolwiek pola? Co się stanie, gdy spróbuję odkryć pole i okaże się ono puste? Dostaję informację tylko o tym polu czy też o polach sąsiednich? Traktowane jest to jako „próba” czy nie? Skoro „liczba pomyłek to próba”, to po co wprowadzasz dwa oznaczenia na to samo?
Podaj dokładny przykład z jakimś działaniem, bo póki co nie wiadomo co w ogóle można robić i jakie są konsekwencje.