Keyboarding (how to find shortest path)

Question

0.00/5 (No votes)

See more:

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?

Posted 10-Sep-16 12:17pm

Member 12731860

Updated 13-Sep-16 2:17am

Patrice T

v2

Add a Solution

Comments

Patrice T 10-Sep-16 19:29pm

Look at
Taxicab geometry - Wikipedia, the free encyclopedia[^]

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2016-09-10T22:18:00

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://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 · Answer 2 · 2016-09-13T02:17:00

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

Keyboarding (how to find shortest path)

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Keyboarding (how to find shortest path)

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us