Quote:
I read about Dijkstra's algorithm, how can you use in this problem?
You don't, it is not for this kind of problem.
In contests like this one, it is never a classical problem, and well known solutions do not apply.
In example 1, the distance between 2 keys mach
Taxicab geometry - Wikipedia, the free encyclopedia[
^].
But when keys are repeating, it don't,
you have to devise your own algorithm.
Dijkstra's algorithm - Wikipedia, the free encyclopedia[
^]
And you have to be careful with examples given:
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
is claimed with best solution 7 with:
Select Left Left Left Select Down Select
But if you do:
Select Down Select Left Down Select
or
Select Down Left Select Down Select
it is 6
[Update]
I just finished my program
Example 2 is even worst, I get 146 instead of 160.
I finally got it, I skipped
If there is no such unit square, the cursor does not move.
which make some keys unreachable.
My bad.
[Update]
Here is my code, but I fear you will have problems to use it, it is in Clipper Language.
* https:
procedure kb()
cls
* chargement des données
KB_init({"ABCDEFG", "HIJKLMN", "OPQRSTU", "VWXYZ**"}, "CONTEST")
KB_init({"12233445566778899000", "QQWWEERRTTYYUUIIOOPP", "-AASSDDFFGGHHJJKKLL*", "--ZZXXCCVVBBNNMM--**", "--------------------"}, "ACM-ICPC-WORLD-FINALS-2015")
KB_init({"ABCDEFGHIJKLMNOPQZY", "X*****************Y"}, "AZAZ")
KB_init({"AXYB", "BBBB", "KLMB", "OPQB", "DEFB", "GHI*"}, "AB")
return
procedure KB_init(clav, chn)
kb_max= (50+50)*10000
ltr= array(len(clav), len(clav[1]))
mat= array(len(clav), len(clav[1]))
cnt= array(len(clav), len(clav[1]))
for row=1 to len(clav)
afill(mat[row], .f.)
afill(cnt[row], kb_max)
for col=1 to len(clav[1])
ltr[row,col]= substr(clav[row],col,1)
next
? clav[row]
next
mat[1,1l]= .T.
cnt[1, 1]= 0
?
? chn
KB_propag(ltr, mat, cnt)
for scan=1 to len(chn)
touche= chn[scan]
KB_set(ltr, mat, cnt, touche)
KB_propag(ltr, mat, cnt)
* ? touche
best= kb_max
for row=1 to len(mat)
for col=1 to len(mat[row])
if ltr[row, col]= touche
best= min(best, cnt[row, col])
*?? cnt[row, col]
endif
next
next
* ?? best
* inkey(0)
next
* ? "*"
best= kb_max
for row=1 to len(mat)
for col=1 to len(mat[row])
if ltr[row, col]= "*"
best= min(best, cnt[row, col])
* ?? cnt[row, col]
endif
next
next
* ?? best
? best+ len(chn)+ 1
?
?
inkey(0)
return
procedure KB_set(ltr, mat, cnt, touche)
for row=1 to len(mat)
for col=1 to len(mat[row])
if ltr[row, col]= touche
mat[row, col]= .T.
else
mat[row, col]= .F.
cnt[row, col]= kb_max
endif
next
next
return
procedure KB_propag(ltr, mat, cnt)
* calculer la prochaine etape
boucle= .T.
do while boucle
boucle= .F.
for row=1 to len(mat)
for col=1 to len(mat[row])
if mat[row, col]
* est
if col < len(mat[row])
offset=1
do while col+ offset < len(mat[row]) .and. ltr[row, col]= ltr[row, col+ offset]
offset++
enddo
if ltr[row, col] != ltr[row, col+ offset]
if cnt[row, col+ offset] > cnt[row, col]+1
cnt[row, col+ offset] = cnt[row, col]+1
mat[row, col+ offset] = .T.
boucle= .T.
endif
endif
endif
* ouest
if col > 1
offset= -1
do while col+ offset > 1 .and. ltr[row, col]= ltr[row, col+ offset]
offset--
enddo
if ltr[row, col] != ltr[row, col+ offset]
if cnt[row, col+ offset] > cnt[row, col]+1
cnt[row, col+ offset] = cnt[row, col]+1
mat[row, col+ offset] = .T.
boucle= .T.
endif
endif
endif
* sud
if row < len(mat)
offset=1
do while row+ offset < len(mat) .and. ltr[row, col]= ltr[row+ offset, col]
offset++
enddo
if ltr[row, col] != ltr[row+ offset, col]
if cnt[row+ offset, col] > cnt[row, col]+1
cnt[row+ offset, col] = cnt[row, col]+1
mat[row+ offset, col] = .T.
boucle= .T.
endif
endif
endif
* nord
if row > 1
offset= -1
do while row+ offset > 1 .and. ltr[row, col]= ltr[row+ offset, col]
offset--
enddo
if ltr[row, col] != ltr[row+ offset, col]
if cnt[row+ offset, col] > cnt[row, col]+1
cnt[row+ offset, col] = cnt[row, col]+1
mat[row+ offset, col] = .T.
boucle= .T.
endif
endif
endif
mat[row, col]= .F.
endif
next
next
*
if boucle
boucle= .F.
for row= len(mat) to 1 step -1
for col= len(mat[row]) to 1 step -1
if mat[row, col]
* est
if col < len(mat[row])
offset=1
do while col+ offset < len(mat[row]) .and. ltr[row, col]= ltr[row, col+ offset]
offset++
enddo
if ltr[row, col] != ltr[row, col+ offset]
if cnt[row, col+ offset] > cnt[row, col]+1
cnt[row, col+ offset] = cnt[row, col]+1
mat[row, col+ offset] = .T.
boucle= .T.
endif
endif
endif
* ouest
if col > 1
offset= -1
do while col+ offset > 1 .and. ltr[row, col]= ltr[row, col+ offset]
offset--
enddo
if ltr[row, col] != ltr[row, col+ offset]
if cnt[row, col+ offset] > cnt[row, col]+1
cnt[row, col+ offset] = cnt[row, col]+1
mat[row, col+ offset] = .T.
boucle= .T.
endif
endif
endif
* sud
if row < len(mat)
offset=1
do while row+ offset < len(mat) .and. ltr[row, col]= ltr[row+ offset, col]
offset++
enddo
if ltr[row, col] != ltr[row+ offset, col]
if cnt[row+ offset, col] > cnt[row, col]+1
cnt[row+ offset, col] = cnt[row, col]+1
mat[row+ offset, col] = .T.
boucle= .T.
endif
endif
endif
* nord
if row > 1
offset= -1
do while row+ offset > 1 .and. ltr[row, col]= ltr[row+ offset, col]
offset--
enddo
if ltr[row, col] != ltr[row+ offset, col]
if cnt[row+ offset, col] > cnt[row, col]+1
cnt[row+ offset, col] = cnt[row, col]+1
mat[row+ offset, col] = .T.
boucle= .T.
endif
endif
endif
mat[row, col]= .F.
endif
next
next
endif
enddo
return