C# verseny feladat

C# verseny feladat
2021-11-20T20:50:32+01:00
2021-11-21T16:01:29+01:00
2022-08-12T05:45:30+02:00
xerzeus
Sziasztok! Egy kis segítséget szeretnék kérni! Gyakorlás képpen Programozási IV. Nemes Tihamér Nemzetközi Informatikai Tanulmányi Verseny feladatiból szoktam megoldani egy-kettőt, viszont az egyik feladatnál elakadtam és nem tudom, hogy merre induljak el, illetve pontosan, hogyan is kéne megoldani.

A feladat:
Egy négyzet alakú területre falakat helyezünk, amelyek 1 egység széles téglalapok. A téglalapok
oldalai párhuzamosak a négyzet oldalaival. Arra vagyunk kíváncsiak, hogy bizonyos pontokból kiindulva eljuthatunk-e a négyzet szélére úgy, hogy falon nem megyünk át.
Készíts programot, amely kiszámítja, hogy az adott pontokból ki lehet-e jutni a négyzet szélére!
A FALAK.BE állomány első sorában a négyzet oldalhossza (1≤H≤1000), a falak száma (0≤L≤1
0000) és a kiindulási pontok száma (1≤K≤5) van. A következő L sor mindegyike 4 számot tartalmaz, a fal bal alsó sarkának koordinátáit (1≤x,y≤H) és a fal oldalhosszait (1≤x+dx, y+dy≤H; dx és dy közül az egyik biztosan 1). Az utolsó K sorban a K kezdőpont koordinátái vannak (1≤kx,ky≤H)

A FALAK.KI állományba K sort kell írni! Ha az I-edik pontból ki lehet jutni, akkor az I-edik sorba az IGEN szó kerüljön, egyébként pedig a NEM! Ha a kezdőpont fal belsejében van, akkor is a
NEM szót kell kiírni.

Példa:
FALAK.BE             FALAK.KI
10 5 3                    IGEN
2 2 1 4                   NEM
4 2 5 1                   NEM
3 5 6 1
5 3 1 2
8 3
1 2
4 4
6 3
2 5

Már azért is hálás lennék, ha valaki leírja, hogy hogyan induljak el vagy pontosan milyen témakört dolgozz fel a feladat!
Mutasd a teljes hozzászólást!
Vegyük a példa feladatot. A példa input első sora az, hogy: 10 5 3. Ez azt jelenti, hogy 10*10-es négyzetünk van, 5 fallal (a harmadik az most minket nem érdekel).

Valahogy tárolnunk kell a memóriában a pályát, és jelölnünk kell, hogy az pályán egy adott koordináta falat vagy nem falat jelent-e. Szóval ehhez töltsünk fel egy mátrixot, amelyben mondjuk a 0 jelenti a nem falat, az 1 pedig a falat.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Ezt követően olvassuk fel sorra a falak adatait. A kiindulási koordináta egyértelmű, arra kell figyelni, hogy a fájlban 1-től indexel, a C# pedig nullától, szóval ez ne zavarjon össze. Az első fal adatai pedig 2 2 1 4, vagyis a (2, 2) pontban kezdődik, 1 széles és 4 magas. Valójában ez azt jelenti, hogy a kiinduló koordinátából:
- ha az adatok közül a harmadik számjegy volt az 1-es, akkor a falunk függőleges
- ha a negyedik számjegy volt az 1-es, akkor vízszintesen kell menni.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
A következő fal: 4 2 5 1:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
A harmadik fal 3 5 6 1:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
A negyedik fal 5 3 1 2:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Az ötödik pedig 8 3 1 2 (itt volt egy kis hiba a példa input tördelésében):

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Kezdésnek juss el addig, hogy a fájlt be tudod tölteni és ezeket a mezőket be tudod állítani :)
Mutasd a teljes hozzászólást!

  • De tessék, itt a megoldás:

    using System; public class Program { public static void Main() { //az előző példámban a koordinátarendszer //origója a bal alsó sarokban volt, de //programozás-technikailag a bal felső lesz az //tehát az X tengely lefelé tart, az Y pedig jobbra int[,] matrix = new int[10,10] { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; Console.WriteLine(HasWayOut(matrix, (3, 3))); Console.WriteLine(HasWayOut(matrix, (5, 2))); Console.WriteLine(HasWayOut(matrix, (1, 4))); } public static int[,] CloneMatrix(int[,] matrix) { int rows = matrix.GetLength(0); int cols = matrix.GetLength(1); int[,] result = new int[rows, cols]; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) result[i, j] = matrix[i, j]; return result; } public static bool HasWayOut(int[,] matrix, (int X, int Y) currentPosition) { int x = currentPosition.X; int y = currentPosition.Y; //ha falban vagyunk, akkor nincs kiút if (matrix[x, y] == 1) return false; int rows = matrix.GetLength(0); int cols = matrix.GetLength(1); //ha a pálya szélén vagyunk, akkor kijutottunk if (x == 0 || y == 0 || x == rows-1 || y == cols-1) return true; //nézzük meg, mely irányokba tudunk menni bool canMoveUp = y > 0 && y < cols-1 && matrix[x, y+1] == 0; bool canMoveDown = y > 0 && y < cols-1 && matrix[x, y-1] == 0; bool canMoveLeft = x > 0 && x < rows-1 && matrix[x-1, y] == 0; bool canMoveRight = x > 0 && x < rows-1 && matrix[x+1, y] == 0; //készítsünk egy másolatot a mátrixról és az aktuális pozíciónk helyére //tegyünk egy falat, jelezvén, hogy oda már nem tudunk lépni //különben mehetnénk a végtelenségig int[,] matrixClone = CloneMatrix(matrix); matrixClone[x, y] = 1; if (canMoveUp && HasWayOut(matrixClone, (x, y+1))) return true; if (canMoveDown && HasWayOut(matrixClone, (x, y-1))) return true; if (canMoveLeft && HasWayOut(matrixClone, (x-1, y))) return true; if (canMoveRight && HasWayOut(matrixClone, (x+1, y))) return true; return false; } }
    Mutasd a teljes hozzászólást!
  • Miért oldod meg neki teljesen?
    Mutasd a teljes hozzászólást!
  • Igazad van abban, hogy nem kellene, de a feladatot tartalmazó könyv eleve fent van a neten, amiben benne van a megoldás, szóval végső soron a kérdező lelkiismeretén áll vagy bukik a dolog. Ha komolyan érdekli a programozás, akkor követheti azt a tippet, amit az első hozzászólásomban adtam neki, és nagyon szívesen segítek neki a továbbiakban is. Az ő dolga, hogy tanulni akar-e és összerakja magától, vagy a könnyebbik utat választja.
    Mutasd a teljes hozzászólást!
  • Nagyon szépen köszönöm! Már ez egy hatalmas segítség, csak az elinduláshoz kellett egy lökés, mert nem voltam benne biztos, hogy mégis hogyan, de én is a mátrixon agyaltam.

    Kedves tőled, hogy ilyen részletesen leírtad, időt fordítottál rá és segítettél nekem! :)
    Mutasd a teljes hozzászólást!
  • Hali!

    1. A jövőben mutasd – lehetőleg forráskóddal/-részlettel –, hogy eddig mivel, hogyan próbálkoztál, meddig jutottál el, mi nem megy, miben/hol akadtál el!
    2. Próbálj meg normális, a problémát jól körülíró címet adni a témádnak!

    Mutasd a teljes hozzászólást!
abcd