Algoritmos: Campo Minado (Minesweeper)

Escrito por

Continuando nossa série sobre algoritmos que são utilizados em questões de competições/maratonas de programação e em entrevistas, neste post, iremos tratar sobre o algoritmo campo minado (minesweeper), retirado do livro Programming Challenges de Miguel Skiena. No vídeo, explico detalhadamente sobre o algoritmo e como resolvê-lo.

1const input = \`4 4
2\*...
3....
4.\*..
5....
63 5
7\*\*...
8.....
9.\*...
100 0\`
11
12let lines = input.split('\\n')
13
14let current = 0
15let currentField = 1
16
17function minesweeper(field, numCols){
18 let filledField = \[\]
19 const len = field.length
20 for(let i = 0; i<len; i++){
21 let line = \[\]
22 for(let k=0; k<numCols; k++){
23 if(field\[i\].charAt(k)==='\*'){
24 line.push('\*')
25 }else{
26 line.push(0)
27 }
28 }
29 filledField.push(line)
30 }
31 for(let i = 0; i<len; i++){
32 for(let k=0; k<numCols; k++){
33 if(filledField\[i\]\[k\]!=='\*'){
34 if(i>0){
35 if(k>0){
36 if(filledField\[i-1\]\[k-1\]==='\*'){
37 filledField\[i\]\[k\]++
38 }
39 }
40 if(filledField\[i-1\]\[k\]==='\*'){
41 filledField\[i\]\[k\]++
42 }
43 if(k+1<numCols){
44 if(filledField\[i-1\]\[k+1\]==='\*'){
45 filledField\[i\]\[k\]++
46 }
47 }
48 }
49
50 if(k>0){
51 if(filledField\[i\]\[k-1\]==='\*'){
52 filledField\[i\]\[k\]++
53 }
54 }
55 if(k+1<numCols){
56 if(filledField\[i\]\[k+1\]==='\*'){
57 filledField\[i\]\[k\]++
58 }
59 }
60
61 if(i+1<len){
62 if(k>0){
63 if(filledField\[i+1\]\[k-1\]==='\*'){
64 filledField\[i\]\[k\]++
65 }
66 }
67 if(filledField\[i+1\]\[k\]==='\*'){
68 filledField\[i\]\[k\]++
69 }
70 if(k+1<numCols){
71 if(filledField\[i+1\]\[k+1\]==='\*'){
72 filledField\[i\]\[k\]++
73 }
74 }
75 }
76 }
77 }
78 }
79 for(let i=0; i<len; i++){
80 console.log(filledField\[i\].join(''))
81 }
82 console.log('')
83}
84
85do{
86 line = lines\[current++\]
87 let nums = line.split(' ')
88 if(nums.length===2){
89 const numLines = parseInt(nums\[0\])
90 const numCols = parseInt(nums\[1\])
91 if(numLines!==0 && numCols!==0){
92 console.log('Field #'+currentField+':')
93 minesweeper(lines.slice(current, current+numLines), numCols)
94 currentField++
95 }
96 }
97}while(line !== '0 0')

Caso tenha ficado alguma dúvida, comente aqui embaixo e fique à vontade também para mandar sugestões. Cadastre seu e-mail para receber nossas últimas novidades. Abraços!

Evolua mais rápido

Junte-se a milhares de desenvolvedores no nosso time de alunos premium e alcance mais rápido o próximo nível da sua carreira.

Ver cursos Premium