Nosaukums
Mīnu laukums (minesweeper2)
Laika limits
2.00s
Atmiņas limits
128.0 MB
Grūtība
32%

Definīcija

Savulaik populāra bija datorspēle “Minesweeper”, kas tika spēlēta uz N×M rūtiņu  liela laukuma un kurā bija nepieciešams noteikt, kurās rūtiņās atrodas mīnas un kurās rūtiņās mīnu nav. Viens, pilnībā atrisināts laukums parādīts zīmējumā. Ar karodziņiem atzīmētas rūtiņas, kurās ir mīnas, bet skaitļi rūtiņās nozīmē, cik mīnu ir tās kaimiņu rūtiņās. Rūtiņas atrodas kaimiņos, ja tām ir kaut viens kopīgs punkts. Tukšajām rūtiņām kaimiņos mīnu nav - var uzskatīt, ka šajās rūtiņās ir ierakstītas nulles. Uzrakstiet programmu, kas dotajam laukuma izmēram un mīnu novietojumam aprēķina tukšo rūtiņu skaitu, kurām kaimiņos mīnu nav, kurām kaimiņos ir viena, divas, …, astoņas mīnas!

Minesweeper spēles piemērs


Ievaddatu raksturojums

Pirmajā rindā doti trīs naturāli skaitļi, kas atdalīti ar tukšumzīmēm: N (1≤N≤109 ) – laukuma rindu skaits, M (1≤M≤109 ) – laukuma kolonnu skaits, B (1≤B≤min(105 ,N×M)) – mīnu skaits laukumā. Katrā nākamajā rindā doti divi ar tukšumzīmi atdalīti naturāli skaitļi ri(1≤ri≤N) un ki(1≤ki≤M), kas norāda i-tās (1≤i≤B) mīnas koordinātas – rūtiņas rindas un kolonnas numuru. Laukuma rindas un kolonnas ir numurētas ar naturāliem skaitļiem pēc kārtas, sākot no 1. Katrā rūtiņā var būt ne vairāk kā viena mīna. 


Izvaddatu raksturojums

Programmai jāanalizē tās laukuma rūtiņas, kurās mīnu nav, un jāizvada deviņi veseli nenegatīvi skaitļi – laukuma rūtiņu skaits, kurām kaimiņos mīnu nav, kurām kaimiņos ir viena, divas, ..., astoņas mīnas. Starp katriem diviem skaitļiem izvaddatos jābūt vienai tukšumzīmei. 


Piezīmes

Apakšuzdevumi

  • B = 1 (4 punkti)
  • Nevienai rūtiņai blakus nav vairāk kā viena mīna (6 punkti)
  • N = 1 vai M=1 (10 punkti)
  • N ≤ 1000, M ≤ 1000 (20 punkti)
  • N×M < 106 (20 punkti)
  • B < 1000 (20 punkti)

Paraugdati

Stdin
8 9 10
3 4
1 2
7 7
4 9
1 4
6 6
1 6
6 7
1 9
7 2
Stdout
19 32 8 3 0 0 0 0 0

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.