今日の問題
↑押してください。
自分の回答(javascript)
function Main(input){
min = 1e18
max = -1e18
let abc = "abcdefghijklmnopqrstuvwxyz".split("")
let ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("")
let f = 3
if(f == 0){
input = parseInt(input.trim())
}
if(f == 1){
input = input.trim().split("\n").map((a)=>parseInt(a))
}
if(f == 2){
input = input.trim().split("\n").map((a)=>a.split(" ").map((b)=>parseInt(b)))
}
res = 0
input = input.trim().split("\n")
let [h,w,d] = input.shift().split(" ").map((a)=>parseInt(a))
let s = input.map((a)=>a.split(""))
hlist = []
for(let i = 0;i<h;i++){
for(let j = 0;j<w;j++){
if(s[i][j] == "H"){
hlist.push([i,j])
}
}
}
map = []
for(let i = 0;i<h;i++){
map.push(new Array(w).fill(-1))
}
let bfs = []
for(let i = 0;i<hlist.length;i++){
map[hlist[i][0]][hlist[i][1]] = 0
bfs.push([hlist[i][0],hlist[i][1],0])
}
let a = 0
while(a<bfs.length){
if(bfs[a][2] == 2){
//console.log(map.join("\n"))
}
y = bfs[a][0]
x = bfs[a][1]
//console.log(y,x)
let list = [[-1,0],[0,1],[1,0],[0,-1]]
for(let i = 0;i<4;i++){
let ny = y+list[i][0]
let nx = x+list[i][1]
//console.log(ny,nx)
if(0<=ny && ny<h && 0<=nx && nx<w && map[ny][nx] == -1 && s[ny][nx] == "."){
bfs.push([ny,nx,bfs[a][2]+1])
map[ny][nx] = bfs[a][2]+1
}
}
a++
}
count = 0
for(let i = 0;i<h;i++){
for(let j = 0;j<w;j++){
if(map[i][j] != -1){
if(map[i][j] <= d){
count ++
}
}
}
}
console.log(count)
function dfs(y,x,depth){
}
}
Main(require("fs").readFileSync(0, "utf8"));
//ここより上は定型文です。
工夫した点
bfsで解きます。幅優先探索のため、すでに訪れている箇所は更新しなくてよいです。理由はそれより前に訪れているのであれば、そっちのほうが最小だからです。表を作っていくという点では、DPに似たものを感じます。