Zadatak s natjecanja i opce pitanje

poruka: 4
|
čitano: 1.886
|
moderatori: Lazarus Long, XXX-Man, vincimus
1
+/- sve poruke
ravni prikaz
starije poruke gore
12 godina
neaktivan
offline
Zadatak s natjecanja

Pozdrav,

 

Ovo je bio najtezi zadatak na proslogodisnjem zupanijskom natjecanju iz informatike

Htio bih da mi ga netko rijesi sa sto detaljnijim objasnjenjem u pythonu, na sluzbenim rjesenjima je rjesen samo u c++ koji trenutno ne koristim, ne znam toliko...

Ako ne navedeno barem detaljno objasnjenje opcenito kako bi trebao pristupiti ovakvom zadatku...

U skoli nemamo dodatnu nastavu da nas pripremi za ovako nesto... Nitko u nasoj zupaniji nije znao to rjesiti...

 

 

 
1 0 hvala 0
12 godina
neaktivan
offline
Re: Zadatak s natjecanja

Evo rješenja, mislim da je dovoljno jednostavno da nisu potrebna dodatna pojašnjenja.

 

def učitaj(ime_datoteke):
    """Učitaj podatke iz datoteke"""
    with open(ime_datoteke) as f:
        prvi_redak = f.readline().split()
        raspored = [list(redak.rstrip()) for redak in f]
    broj_redaka = int(prvi_redak[0])
    broj_stupaca = int(prvi_redak[1])
    return broj_redaka, broj_stupaca, raspored


def eksplodiraj(broj_redaka, broj_stupaca, raspored, redak_bombe, stupac_bombe):
    """Uništi mete u dometu bombe i vrati njihov broj"""
    broj_meta = 0
    for r in range(redak_bombe - 5, redak_bombe + 6):
        if 0 <= r < broj_redaka and raspored[r][stupac_bombe] == '#':
            broj_meta += 1
            raspored[r][stupac_bombe] = '.'
    for s in range(stupac_bombe - 5, stupac_bombe + 6):
        if 0 <= s < broj_stupaca and raspored[redak_bombe][s] == '#':
            broj_meta += 1
            raspored[redak_bombe][s] = '.'
    return broj_meta


def riješi(ime_datoteke):
    broj_meta = 0
    broj_načina = 0
    broj_redaka, broj_stupaca, raspored = učitaj(ime_datoteke)
    broj_polja = broj_redaka * broj_stupaca

    for bomba1 in range(broj_polja - 1):
        redak_bomba1, stupac_bomba1 = divmod(bomba1, broj_stupaca)
        for bomba2 in range(bomba1 + 1, broj_polja):
            redak_bomba2, stupac_bomba2 = divmod(bomba2, broj_stupaca)

            kopija_rasporeda = [redak[:] for redak in raspored]
            novi_broj_meta = eksplodiraj(broj_redaka, broj_stupaca, kopija_rasporeda, redak_bomba1, stupac_bomba1)
            novi_broj_meta += eksplodiraj(broj_redaka, broj_stupaca, kopija_rasporeda, redak_bomba2, stupac_bomba2)
            if novi_broj_meta > broj_meta:
                broj_meta = novi_broj_meta
                broj_načina = 1
            elif novi_broj_meta == broj_meta:
                broj_načina += 1

    return broj_meta, broj_načina


for test in ['test1', 'test2', 'test3']:
    broj_meta, broj_načina = riješi(test)
    print(broj_meta)
    print(broj_načina)

 

Program koristi testne podatke pripremljene u datotekama test1, test2 i test3.

17 godina
offline
Zadatak s natjecanja i opce pitanje

Može i rekurzijom, dubinom rekurzije na 5 postignemo da od točke pretrage obuhvatimo kvadrat od 5 polja sa svake strane, uz to gledamo samo polja u istom retku i stupcu kao početno polje.

 

#include<iostream>

using namespace std;

char ploca[300][301];
int R, S, ukupnoMeta=0, brojNacina=0;

void bombe(int x, int y, int a, int b, int granica)
{
   if (x< 0 || y <0 || x>R - 1 || y>S - 1) return;
   if (x != a && y != b) return;
   if (granica > 5) return;

   if (ploca[x][y] == '#') ploca[x][y] = '$';

   bombe(x - 1, y, a, b, granica + 1);
   bombe(x + 1, y, a, b, granica + 1);
   bombe(x, y - 1, a, b, granica + 1);
   bombe(x, y + 1, a, b, granica + 1);
}

int main()
{
   int brojPolja, brojMeta;
   cin >> R >> S;
   brojPolja = R * S;
   for (int i = 0; i < R; i++)
   {
      cin >> ploca[i];
   }
   for (int i = 0; i < brojPolja - 1; i++)
   {
      for (int j = i+1; j < brojPolja; j++)
      {
         bombe(i / S, i % S, i / S, i % S, 0);
         bombe(j / S, j % S, j / S, j % S, 0);
         brojMeta = 0;
         for (int k = 0; k < brojPolja; k++)
         {
            if (ploca[k / S][k % S] =='$')
            {
               brojMeta++;
               ploca[k / S][k % S] = '#';
            }
         }
         if (brojMeta > ukupnoMeta)
         {
            ukupnoMeta = brojMeta;
            brojNacina = 1;
         }
         else if (brojMeta == ukupnoMeta)
            brojNacina++;
      }
   }
   cout << ukupnoMeta << "\n" << brojNacina << endl;
   return 0;
}

Poruka je uređivana zadnji put pet 19.6.2015 17:26 (Floki).
 
1 0 hvala 0
12 godina
neaktivan
offline
Zadatak s natjecanja i opce pitanje

Hvala :D

 
0 0 hvala 0
1
Nova poruka
E-mail:
Lozinka:
 
vrh stranice