Hi.
I'm sorry. I have a question but I couldn't solve it. it doesn't belong to codeforces. In this question, we have a n * n
matrix and we want to go from (1,1)
to (n,n)
. we only can move left, right, up, down. but there is a special tag on some cells. if we are in a cell and there is a special tag around us (I mean 8 side of a cell), we can move directly to that. Question guaranteed that each row and each cell contain exactly one tag.
We want to find minimum move to go from (1,1)
to (n,n)
.
Question give information in special way. for example:
Input 1:
3
1 2 3
Output 1:
2
Input 2:
4
2 3 1 4
Output 2:
4
in first row, n
will given. in next row, n
numbers will given. The i
-th number mean which row in i
-th column contain tag. range of n
is 1 <= n <= 300000
.
memory limit is 256Mb
Time limit is one second
I think solution is dynamic programming (dp). Because of memory limit , we can't construct a 2D array for out dynamic programming but because we always need just two last state, I only use 3 array for dp. It solves memory limit however time limit is one second and my dp algorithm which calculate all way, failed. it is a simple dp. it calculate 3 state (go down, right and diagonal for special tag). Is it possible to give me a better way?
I'm sorry for bad English. Thanks.