shinjin
BAN USERAssuming, that we basically want collapse repetitions to <character><count> format. E.g. "HHHHHHHHHHELLLLLLLLLLLLPPPP ME BOBBBBBB" becomes "H10EL12P4 ME BOB6"
Also, assuming numbers are not allowed in the input.
int msd(int& k)
{
int d=1;
while (k>=d*10) d *= 10;
int r = k/d;
k %= d;
return r;
}
void compress(char *str)
{
if (str[0]==0) return;
size_t i=0, j=1;
while (str[j]) {
while (str[i] == str[j]) j++;
if (j-i>1) {
int cnt = j-i;
while (cnt>=10)
str[++i] = '0'+msd(cnt);
str[++i] = '0'+msd(cnt);
int ii = i+1;
while ((str[ii++]=str[j++]));
j = ++i+1;
} else {
i = j++;
}
}
}
DFS won't find the shortest path. BFS would.
Imagine, this is your maze:
If you order cell neighbors as RIGHT, BOTTOM, LEFT, TOP, then DFS would return with the longer route.
- shinjin February 24, 2014For other ordering, you can tweak the example to show, that that won't work either.