Fişierul intrare/ieşire:gravity.in, gravity.outSursăAlgoritmiada 2016, Runda Finala, Seniori
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gravity

În această problemă trebuie să simulaţi căderea unor obiecte bidimensionale care urmează reguli asemănătoare (dar nu identice) cu regulile jocului Tetris.

Mai exact, vi se dă o matrice de dimensiuni N x M cu celule de tip . sau #. Liniile sunt numerotate crescător, de la 1 la N, de sus în jos. Numim obiect fiecare componentă maximală 4-conexă de celule de tip #. Toate obiectele cad cu aceeaşi viteză în jos (în direcţia liniei cu numărul N). Dacă un anumit obiect ar ieşi (chiar şi parţial) din matrice prin continuarea mişcării, acesta se opreşte în întregime. Dacă un anumit obiect s-ar intersecta cu un alt obiect (chiar şi parţial) prin continuarea mişcării, acesta se opreşte de-asemenea în întregime. Notaţi că obiectele îşi menţin structura originală pe tot parcursul mişcării, ignorând cu nonşalanţă noţiuni ca "rezistenţa materialelor" sau "stare de echilibru". Puteţi consulta exemplele pentru clarificări.

Voi trebuie să afişaţi starea finală a matricei (i.e starea matricei după ce toate obiectele şi-au încetat mişcarea).

Date de intrare

Fişierul de intrare gravity.in va conţine pe prima sa linie dimensiunile matricei, N şi M. Următoarele N linii vor conţine câte un şir de M caractere de tip . sau #, reprezentând starea iniţială a matricei.

Date de ieşire

În fişierul de ieşire gravity.out se vor afla N linii, fiecare conţinând un şir de M caractere, reprezentând starea finală a matricei.

Restricţii

  • 1 ≤ N, M ≤ 1750
  • Atenţie, memoria pentru stivă este de 8 MB.
  • Termenul de 4-conex se referă la faptul că două celule sunt considerate vecine doar pe cele 4 direcţii (nord, sud, est, vest).
  • Pentru teste grupate în valoare de 32 de puncte, 1 ≤ N, M ≤ 400.
  • Pentru teste grupate în valoare de 14 puncte, toate piesele sunt dreptunghiuri de înălţime 1.
  • Pentru teste grupate în valoare de 51 de puncte, rămân valabile restricţiile generale.
  • Ultimul test de feedback valorează 3 puncte şi este singur în grupă :).

Exemplu

gravity.ingravity.out
10 10
..........
..######..
..#....#..
..#.#..#..
..#..#.#..
..#....#..
..######..
..........
..#....#..
.......#..
..........
..........
..######..
..#....#..
..#....#..
..#....#..
..#.##.#..
..######..
.......#..
..#....#..
10 10
...#......
...#.###..
..........
.#####....
.....#.##.
.....#.##.
..#.......
..#..##...
..#...#.#.
..........
..........
..........
..........
...#......
...#.###..
.#####....
.....#....
..#..#.##.
..#..####.
..#...#.#.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?