10949 - Kids in a Grid

[wook]

I'm getting the same trouble.
I have tried it with gets() and char by char but always get RE by the same cause assert(x>=0 && y>=0 && x<H && y<W).
Could you say me how is yours parse input, please?
I don't understand what is the reason of my RE by this cause.
Thanks!

Two kids NEVER get out of the grid,

if you gets RE with assert(), there might be some errors in input processing.


Notice that
there can be a null-string, i.e. the length is 0,

Code: Select all

2
3 3
ABC
DEF
GHI
0 2 2

0 3 1

3 3
ABC
DEF
GHI
0 1 1

0 1 1

if one uses scanf("%s"), it will omit the empty-string.
also, using gets(), code should be more careful, I think.

[polone]

sorry I didn't explain my mistake

[Emilio]

Thanks wook!
But your case is considered in my parse input method.
Sorry but have posted my code.
I'm getting RE and can't find any bug.
Could you say me if my parse input method is wrong?

Code: Select all

struct stmv {int x,y;};
stmv movs[256];
char s1[30000], s2[30000], s[30000], m[30][30];

main ()
{
    int x, y, H, W, len1, len2, i, cases, kase;
    
    movs['E'].x=0, movs['E'].y=1;
    movs['W'].x=0, movs['W'].y=-1;
    movs['N'].x=-1, movs['N'].y=0;
    movs['S'].x=1, movs['S'].y=0;
    
    gets(s);
    sscanf(s,"%d",&cases);
    for (kase=1; kase<=cases; kase++)
    {
        gets(s);
        sscanf(s,"%d%d",&H,&W);
        for (i=0; i<H; i++) gets(m[i]);
        gets(s);
        sscanf(s,"%d%d%d",&len1,&x,&y);
        x--, y--;
        gets(s);
        for (i=0; i<len1; i++)
        {
            // With this small assert I get: Runtime Error  (SIGABRT)
            assert(x>=0 && y>=0); 
            s1[i]=m[x][y];
            x+=movs[s[i]].x;
            y+=movs[s[i]].y;
        }
        s1[len1++]=m[x][y];       
        s1[len1]=0;
        
        gets(s);
        sscanf(s,"%d%d%d",&len2,&x,&y);
        x--, y--;
        gets(s);
        for (i=0; i<len2; i++)
        {
            // With this small assert I get: Runtime Error  (SIGABRT)
            assert(x>=0 && y>=0); 
            s2[i]=m[x][y];
            x+=movs[s[i]].x;
            y+=movs[s[i]].y;
        }
        s2[len2++]=m[x][y];
        s2[len2]=0;
        
        int n=LCS(s1,s2);
        
        cout << "Case " << kase << ": " << len1-n << " " << len2-n << "\n";
    } 
}

Thanks!

[wook]

Dear Emilio,

I can't find a special miss in your input processing;


this is input procedure of my program, which got AC :

Code: Select all

	int i, x, y;
	scanf("%d %d", &h, &w);

	for(i=1; i<=h; ++i)
		scanf("%s", ma[i] + 1);

	/* first kid */
	scanf("%d", &n);
	gets(temp);
	sscanf(temp, "%d %d", &x, &y);
	gets(temp + 2);

	ip1[1] = ma[x][y];
	for(i=2; temp[i]; ++i)
	{
		switch(temp[i])
		{
		case 'N': --x; break;
		case 'S': ++x; break;
		case 'W': --y; break;
		case 'E': ++y; break;
		}

		ip1[i] = ma[x][y];
	}
	

for the second kid, it is same as the first kid, so it was omitted.

ma[][] is a map, ip1[1..N+1] is a string which is made of kid's step.


Hope it works.

[Emilio]

Thanks another time wook!

I have sent my code with a similar parse input method as yours, and now seem that works fine. Albuit I don't understand why my parse input method don't work.
By other hand I'm getting TLE, but this is another task . I'll try with some algorithm of your recommended papers.

Thanks one more time!

[wook]

yeah, I think that the input file used in judge includes some inappropriate blank lines or blanks

Good Luck..~~

wook

[mysword]

wa....
can anyone give some input-output?
//bow

[polone]

hmm...

WA shouldn't be the problem

I think you may have to check your algo

if the algo is correct there is hard to exist a data to result in WA

[DJWS]

Hiya.

I found an useful link when googling. Right here:
http://cs.haifa.ac.il/LANDAU/courses/Seminar/Lect3.ppt
Simple and fast linear space computation of Longest common subsequences, Claus Rick, 1999

I have a question. Page 33 says:
Finding the dominant matches each contour: O(min(m, (n-p))
I wonder how to implement it?

--
DJWS, a newbie in programming

[DJWS]

No one reply.
However it's a hard problem. I just have seen 20 people who solve.

If the reference posted above is not proper to solve this problem, please correct me. I just think the time complexity told by that reference is similar to the papar mentioned by Adrian Kuegel. And one advantage, the reference is so graphy. (filled with colorful graph )

I still do not know how to calculate dominant matches in good reasonable time like O(min(m, (n-p)). I will keep trying to implement it since I have time.
--
DJWS, a newbie in programming

[chrismoh]

The min(m,n-p) bound comes from the fact that there are most min(m,n-p) dominant matches per contour.

Unfortunately, most papers I have found don't mention how to get min(m,n-p) time per contour - they just state it as fact. (Getting O(m) is really easy, though). And I don't know where you can find Rick's paper online. I have full access to portal.acm.org (through school) and I don't think its there (its only on citations).

I used the algorithm mentioned in this paper:

http://www.stringology.org/event/1999/psc99p4_ps.gz

It has the same worst-case bound as Rick's algorithm, but calculates "all contours" at the same time, instead of calculating contours one at a time.

It's far less colourful and easy to read than the presentation, though

[DJWS]

Unfortunately, most papers I have found don't mention how to get min(m,n-p) time per contour - they just state it as fact. (Getting O(m) is really easy, though).

I agree you. Maybe there is a way to satisfy that condition, but having no idea about it now. Keep discussing anyway.

And I don't know where you can find Rick's paper online. I have full access to portal.acm.org (through school) and I don't think its there (its only on citations).

In fact I have no Rick's paper though I surf hard. It seems papers are unreachable via Internet. I will seek the journal if necessary. And if I find anything in addition, I'd like to post here.

I am going to study this new paper. Thank for your help.
--
DJWS, a newbie in programming

[just_yousef]

How to avoid RE in this problem ??

Code: Select all

#include<bits/stdc++.h>
using namespace std;

char grid[22][22], s1[20002], s2[20002];
int t, n, m, k, x, y, l1, l2, cas = 1, mem[20001][20001];

int solve() {
	for (int i = 0; i <= l1; ++i) {
		for (int j = 0; j <= l2; ++j) {
			if (!i || !j)
				mem[i][j] = 0;
			else {
				if (s1[i - 1] == s2[j - 1])
					mem[i][j] = mem[i - 1][j - 1] + 1;
				else
					mem[i][j] = max(mem[i][j - 1], mem[i - 1][j]);
			}
		}
	}
	return mem[l1][l2];
}
int main(int argc, char **argv) {
	//freopen("a.in", "r", stdin);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; ++i)
			scanf(" %s", grid[i]);
		scanf("%d%d%d\n", &k, &x, &y);
		l1 = k;
		--x, --y;
		char c;
		s1[0] = grid[x][y];
		for (int i = 1; i <= k; ++i) {
			c = getchar();
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s1[i] = grid[x][y];
		}
		getchar();
		scanf("%d%d%d\n", &k, &x, &y);
		l2 = k;
		--x, --y;
		s2[0] = grid[x][y];
		for (int i = 1; i <= k; ++i) {
			c = getchar();
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s2[i] = grid[x][y];
		}
		l1++, l2++;
		int ln = solve();
		printf("Case %d: %d %d\n", cas++, l1 - ln, l2 - ln);
	}
	return 0;
}

[brianfry713]

I changed your input parsing and your code got TLE.

Instead of using a single getchar(), try:
while(getchar() != '\n');

Also read the grid one char at a time instead of as a string.

[just_yousef]

Im sorry but is I still don't get the idea, i changed my code to this:

Code: Select all

#include<bits/stdc++.h>
using namespace std;

char grid[22][22], s1[20002], s2[20002];
int t, n, m, k, x, y, l1, l2, cas = 1, mem[20001][20001];

int solve() {
	for (int i = 0; i <= l1; ++i) {
		for (int j = 0; j <= l2; ++j) {
			if (!i || !j)
				mem[i][j] = 0;
			else {
				if (s1[i - 1] == s2[j - 1])
					mem[i][j] = mem[i - 1][j - 1] + 1;
				else
					mem[i][j] = max(mem[i][j - 1], mem[i - 1][j]);
			}
		}
	}
	return mem[l1][l2];
}
int main(int argc, char **argv) {
//	freopen("a.in", "r", stdin);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d\n", &n, &m);
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				scanf(" %c", &grid[i][j]);
		scanf("%d%d%d\n", &k, &x, &y);
		l1 = k;
		--x, --y;
		char c;
		s1[0] = grid[x][y];
		c = getchar();
		int i =1;
		while(c!='\n'){

			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s1[i] = grid[x][y];
			c = getchar();
		}
		getchar();
		scanf("%d%d%d\n", &k, &x, &y);
		l2 = k;
		--x, --y;
		s2[0] = grid[x][y];
		i=1;
		c = getchar();
		while(c!='\n'&& c!=EOF){
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s2[i] = grid[x][y];
			c = getchar();
		}
		l1++, l2++;
		int ln = solve();
		printf("Case %d: %d %d\n", cas++, l1 - ln, l2 - ln);
	}
	return 0;
}