15,903,788 members
See more:
problem explained here Keyboarding &ndash; Kattis, ICPC World Finals[^]

What I have tried:

What I did first was to put all characters in a 2-D array, find where all the letters are in array and adding the absolute value of the difference of the indexes to get shortest path, this only worked for the first example, what would i have to do if there is more than one of the same letter next to each other. what i did won't get the shortest path. I read about Dijkstra's algorithm, how can you use in this problem?
Posted
Updated 13-Sep-16 2:17am
v2
Patrice T 10-Sep-16 19:29pm

## Solution 1

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.

[Update]
Here is my code, but I fear you will have problems to use it, it is in Clipper Language.
```*	https://online.acmicpc.org/problems/keyboard
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```

v5
Member 12731860 13-Sep-16 5:32am
I have tried to do a algorithm but i could get anything working. I don't think you can do it that way
Patrice T 13-Sep-16 5:35am
Do what that way ?
Member 12731860 16-Sep-16 17:27pm
Patrice T 16-Sep-16 17:33pm
Yes, but you will probably not be able to use it.

## Solution 2

I found this solution but its in c++ and I know c#, I dont understand it, can someone please explain

```using namespace std;

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, -1, 0, 1 };
int mv[50][50][4];
int best[50][50];

int _tmain(int argc, _TCHAR* argv[])
{
int Y, X;
while (cin >> Y >> X) {
vector<string> g(Y);
for (int i = 0; i < Y; i++) cin >> g[i];
string message;
cin >> message;
message += '*';

memset(mv, -1, sizeof(mv));
for (int y = 0; y < Y; y++)
for (int x = 0; x < X; x++)
for (int d = 0; d < 4; d++) {
int x2 = x, y2 = y;
for (int n = 0;; n++) {
if (x2 < 0 || x2 >= X || y2 < 0 || y2 >= Y) break;
if (g[y2][x2] != g[y][x]) {
mv[y][x][d] = n;
break;
}
x2 += dx[d]; y2 += dy[d];
}
}

vector<pair<int, pair<short, short> > > cur;
cur.push_back(make_pair(0, make_pair(0, 0)));

for (int i = 0; i < message.size(); i++) {
memset(best, 63, sizeof(best));
vector<pair<short, short> > v;
int dist = 0, curi = 0;
sort(cur.begin(), cur.end());
for (;;) {
if (v.empty()) {
if (curi == cur.size()) break;
dist = cur[curi].first;
}
while (curi < cur.size() && cur[curi].first == dist) {
v.push_back(cur[curi++].second);
}
vector<pair<short, short> > v2;
for (int j = 0; j < v.size(); j++) {
int x = v[j].first, y = v[j].second;
if (best[y][x] <= dist) continue;
best[y][x] = dist;
for (int d = 0; d < 4; d++) if (mv[y][x][d] != -1) {
int x2 = x + dx[d] * mv[y][x][d], y2 = y + dy[d] * mv[y][x][d];
if (best[y2][x2] > dist + 1) {
v2.push_back(make_pair(x2, y2));
}
}
}
v.swap(v2);
dist++;
}

cur.clear();
for (int y = 0; y < Y; y++)
for (int x = 0; x < X; x++) if (g[y][x] == message[i]) {
cur.push_back(make_pair(best[y][x] + 1, make_pair(x, y)));
}
}

int ret = 1000000000;
for (int i = 0; i < cur.size(); i++) ret = min(ret, cur[i].first);
cout << ret << endl;
}```

v4
[no name] 13-Sep-16 9:06am
If you do not know what it's doing, how do you know it's a solution? And, no, no one is going to write a book trying to explain all this code to you.
Patrice T 13-Sep-16 11:00am
And what does it say for example 4 ?
Patrice T 18-Sep-16 10:10am
I don't know where you found this code, but the least I can say is that it look weird.