Member 12731860 Ответов: 2

Кейбординг (как найти кратчайший путь)

проблемы описаны здесь Набор текста на клавиатуре и amp;ndash; это архив, финала чемпионата мира[^]

Что я уже пробовал:

Сначала я поместил все символы в 2-D массив, нашел, где находятся все буквы в массиве, и добавил абсолютное значение разности индексов, чтобы получить кратчайший путь, это сработало только для первого примера, что бы я должен был делать, если рядом друг с другом находится более одной одной буквы. то, что я сделал, не получит кратчайшего пути. Я читал об алгоритме Дейкстры, как вы можете использовать его в этой задаче?

Patrice T

Смотреть на
Геометрия такси-Википедия, свободная энциклопедия[^]

2 Ответов

Рейтинг:
2

Member 12731860

Я нашел это решение, но оно на c++, и я знаю c#, я его не понимаю, может кто-нибудь объяснить

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;
    }

NotPolitcallyCorrect

Если вы не знаете, что он делает,как вы узнаете, что это решение? И нет, никто не напишет книгу, пытаясь объяснить вам весь этот код.

Patrice T

А что там написано, например, 4 ?

Patrice T

Я не знаю, где вы нашли этот код, но самое меньшее, что я могу сказать, это то, что он выглядит странно.

Рейтинг:
0

Patrice T

Цитата:
Я читал об алгоритме Дейкстры, как вы можете использовать его в этой задаче?
Вы этого не сделаете, это не для такого рода проблем.
В таких конкурсах, как этот, это никогда не классическая задача, и хорошо известные решения не применяются.
В Примере 1 расстояние между 2 клавишами Маха Геометрия такси-Википедия, свободная энциклопедия[^].
Но когда клавиши повторяются, это не так, вы должны разработать свой собственный алгоритм.

Алгоритм Дейкстры-Википедия, свободная энциклопедия[^]

И вы должны быть осторожны с приведенными примерами:
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

заявлено с лучшим решением 7 с:
Select Left Left Left Select Down Select

Но если вы это сделаете:
Select Down Select Left Down Select

или
Select Down Left Select Down Select

это 6

[Обновление]
Я только что закончил свою программу
Пример 2 еще хуже, я получаю 146 вместо 160.
Я наконец-то понял это, я пропустил
Если такого единичного квадрата нет, курсор не перемещается.
что делает некоторые ключи недоступными.
Моя вина.

[Обновление]
Вот мой код, но я боюсь, что у вас возникнут проблемы с его использованием, он написан на языке Clipper.
*	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

Member 12731860

Я пытался сделать алгоритм, но у меня ничего не получалось. Я не думаю, что вы можете сделать это таким образом

Patrice T

Что делать таким образом ?

Member 12731860

Могу я посмотреть вашу программу?

Patrice T

Да, но вы, вероятно, не сможете им воспользоваться.