Algoritmos: Campo Minado (Minesweeper)

Algoritmos: Campo Minado (Minesweeper)

Tulio Faria
Tulio Faria24 de fevereiro de 2017
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.
lJbqOpm2WGg
Assistir vídeo

const input = \`4 4 \*... .... .\*.. .... 3 5 \*\*... ..... .\*... 0 0\` let lines = input.split('\\n') let current = 0 let currentField = 1 function minesweeper(field, numCols){ let filledField = \[\] const len = field.length for(let i = 0; i<len; i++){ let line = \[\] for(let k=0; k<numCols; k++){ if(field\[i\].charAt(k)==='\*'){ line.push('\*') }else{ line.push(0) } } filledField.push(line) } for(let i = 0; i<len; i++){ for(let k=0; k<numCols; k++){ if(filledField\[i\]\[k\]!=='\*'){ if(i>0){ if(k>0){ if(filledField\[i-1\]\[k-1\]==='\*'){ filledField\[i\]\[k\]++ } } if(filledField\[i-1\]\[k\]==='\*'){ filledField\[i\]\[k\]++ } if(k+1<numCols){ if(filledField\[i-1\]\[k+1\]==='\*'){ filledField\[i\]\[k\]++ } } } if(k>0){ if(filledField\[i\]\[k-1\]==='\*'){ filledField\[i\]\[k\]++ } } if(k+1<numCols){ if(filledField\[i\]\[k+1\]==='\*'){ filledField\[i\]\[k\]++ } } if(i+1<len){ if(k>0){ if(filledField\[i+1\]\[k-1\]==='\*'){ filledField\[i\]\[k\]++ } } if(filledField\[i+1\]\[k\]==='\*'){ filledField\[i\]\[k\]++ } if(k+1<numCols){ if(filledField\[i+1\]\[k+1\]==='\*'){ filledField\[i\]\[k\]++ } } } } } } for(let i=0; i<len; i++){ console.log(filledField\[i\].join('')) } console.log('') } do{ line = lines\[current++\] let nums = line.split(' ') if(nums.length===2){ const numLines = parseInt(nums\[0\]) const numCols = parseInt(nums\[1\]) if(numLines!==0 && numCols!==0){ console.log('Field #'+currentField+':') minesweeper(lines.slice(current, current+numLines), numCols) currentField++ } } }while(line !== '0 0')

Curta o DevPleno no Facebook, se inscreva no canal no YouTube e cadastre seu e-mail para não perder as atualizações. Abraço!
Tulio Faria
Autor
Tulio Faria24 de fevereiro de 2017

Últimas do Blog