Max length of 1-2-0-2.. diagonal sequence, on cw rotation #hard #dp
Intuition
Do Depth-First Search, add memoization (however accepted without it)
Approach
enumerate diagonals as 0..3, cw rotation is (d+1)%4, ccw (d+3)%4
v is irrelevant to dp key
dp key can be Int: (500*y+x)*100 + dir*10 + rot
I think the HashMap is the weakest point of performance
Complexity
Time complexity: $$O(mn)$$
Space complexity: $$O(n)$$
Code
// 1219ms
fun lenOfVDiagonal(g: Array<IntArray>): Int {
val nxy = arrayOf(-1,-1,1,1,-1); val nv = arrayOf(2,2,0); var res = 0
fun dfs(y: Int, x: Int, dir: Int, rot: Int, v: Int): Int =
if (y !in 0..<g.size || x !in 0..<g[0].size || g[y][x] != v ) 0
else 1 + max(dfs(y+nxy[dir],x+nxy[dir+1],dir,rot,nv[v]),
if (rot > 0) dfs(y,x,(dir+1)%4,0,v)-1 else 0)
for (y in g.indices) for (x in g[0].indices) if (g[y][x] == 1)
res = max(res, (0..3).maxOf {dfs(y,x,it,1,1)})
return res
}
// 981ms
fun lenOfVDiagonal(g: Array<IntArray>): Int {
val nxy = arrayOf(-1,-1,1,1,-1); val nv = arrayOf(2,2,0); var res = 0
val dp = HashMap<Int, Int>()
fun dfs(y: Int, x: Int, dir: Int, rot: Int, v: Int): Int =
if (y < 0 || x < 0 || y == g.size || x == g[0].size || g[y][x] != v ) 0
else 1 + dp.getOrPut((y*500 + x)*100 + dir*10 + rot) { max(
dfs(y+nxy[dir],x+nxy[dir+1],dir,rot,nv[v]),
if (rot > 0) dfs(y,x,(dir+1)%4,0,v)-1 else 0) }
for (y in g.indices) for (x in g[0].indices) if (g[y][x] == 1)
res = max(res, (0..3).maxOf {dfs(y,x,it,1,1)})
return res
}
