键盘（如何找到最短路径） [英] Keyboarding (how to find shortest path)
问题描述
此处解释的问题 Keyboarding& ndash; Kattis，ICPC世界总决赛 [ ^ ]
我尝试了什么：
我先做的是放置所有字符在二维数组中，找到所有字母在数组中的位置，并添加索引差异的绝对值以获得最短路径，这仅适用于第一个示例，如果有多个，我将需要做什么彼此相邻的一封信。我做了什么不会得到最短的路径。我读到了Dijkstra的算法，你怎么能在这个问题中使用？
problem explained here Keyboarding – 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?
推荐答案
我读到了Dijkstra的算法，你怎么能在这个问题上使用？
I read about Dijkstra's algorithm, how can you use in this problem?
你没有，它不适用于这种问题。
在像这样的竞赛中，它从来不是一个经典的问题，众所周知的解决方案也不适用。
在示例1中，两个键之间的距离为出租车几何 - 维基百科，免费百科全书 [ ^ ]。
但是当按键重复时，它没有，你必须设计自己的算法。
Dijkstra的算法 - 维基百科，免费的百科全书 [ ^ ]
你必须小心给出的例子：
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
是最好的解决方案7与：
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
它是6
[更新]
我刚完成了我的程序
示例2甚至最差，我得到146而不是160。
我终于得到了它，我跳过了/>
如果没有这样的单位正方形，则光标不会移动。
使某些键无法访问。
My坏了。
[更新]
这是我的代码，但我担心你会有问题使用它，它是Clipper语言。
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://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
我发现这个解决方案，但它在c ++，我知道c＃，我不明白，有人可以解释
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;
}
这篇关于键盘（如何找到最短路径）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
