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 42\*...3....4.\*..5....63 57\*\*...8.....9.\*...100 0\`1112let lines = input.split('\\n')1314let current = 015let currentField = 11617function minesweeper(field, numCols){18 let filledField = \[\]19 const len = field.length20 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 }4950 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 }6061 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}8485do{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!
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