Click here to Skip to main content
15,903,788 members
Please Sign up or sign in to vote.
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
Updated 13-Sep-16 2:17am
v2
Comments

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
 
Share this answer
 
v5
Comments
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    
Can i see your program?
Patrice T 16-Sep-16 17:33pm    
Yes, but you will probably not be able to use it.
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;
    }
 
Share this answer
 
v4
Comments
[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.

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900