320 - Border

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Thu Apr 10, 2003 4:35 am

Hi,
No Trick at all. Just do what they want.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Why 320 WA

Post by chunyi81 » Sat Jul 05, 2003 5:26 am

I have tried to solove problem 320 Border in Java, tested with many test cases, all of which gives the correct output. But OJ gives WA. Why? Below is the Java source code I wrote for the problem:

[java]import java.io.*;
import java.util.*;
class Main {

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}

catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main(String[] args) {

char [][] bitmap = new char[32][32];
StringTokenizer st = new StringTokenizer(ReadLn(255));
int cases = Integer.parseInt(st.nextToken());

for (int i = 1;i <= cases;i++) {

if (i > 1)
System.out.println();

st = new StringTokenizer(ReadLn(255));
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(ReadLn(255));
String moves = st.nextToken();
int index = 0;

initialise(bitmap);

while(moves.charAt(index) != '.') {

if (moves.charAt(index) == 'N') {

y++;
bitmap[x][y - 1] = 'X';

}

else if (moves.charAt(index) == 'E') {

x++;
bitmap[x - 1][y - 1] = 'X';

}

else if (moves.charAt(index) == 'S') {

y--;
bitmap[x - 1][y] = 'X';

}

else if (moves.charAt(index) == 'W') {

x--;
bitmap[x][y] = 'X';

}

index++;

}

System.out.println("Bitmap #" + i);
print_bitmap(bitmap);

}

}

public static void initialise(char[][] bitmap) {

for (int i = 0;i < bitmap.length;i++)
for (int j = 0;j < bitmap[0].length;j++)
bitmap[j] = '.';

}

public static void print_bitmap(char[][] bitmap) {

for (int i = bitmap[0].length - 1;i >= 0;i--) {
for (int j = 0;j < bitmap.length;j++)
System.out.print(bitmap[j]);

System.out.println();
}

}

}[/java]

Let me explain the algorithm I used. I tried to work out the corresponding coordinates of the set bits as I move along the path, and set them to 'X' in the only 2D char array that I used. The array is inititalised such that all elements are '.'(periods). What is wrong with my algorithm? Is there any special test cases I overlooked? Thanks.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

320 - Border

Post by chunyi81 » Mon Jul 07, 2003 6:11 am

[java]import java.io.*;
import java.util.*;
class Main {

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}

catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main(String[] args) {

char [][] bitmap = new char[32][32];
StringTokenizer st = new StringTokenizer(ReadLn(255));
int cases = Integer.parseInt(st.nextToken());

for (int i = 1;i <= cases;i++) {

if (i > 1)
System.out.println();

st = new StringTokenizer(ReadLn(255));
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(ReadLn(255));
String moves = st.nextToken();
int index = 0;

initialise(bitmap);

while(moves.charAt(index) != '.') {

if (moves.charAt(index) == 'N') {

y++;
bitmap[x][y - 1] = 'X';

}

else if (moves.charAt(index) == 'E') {

x++;
bitmap[x - 1][y - 1] = 'X';

}

else if (moves.charAt(index) == 'S') {

y--;
bitmap[x - 1][y] = 'X';

}

else if (moves.charAt(index) == 'W') {

x--;
bitmap[x][y] = 'X';

}

index++;

}

System.out.println("Bitmap #" + i);
print_bitmap(bitmap);

}

}

public static void initialise(char[][] bitmap) {

for (int i = 0;i < bitmap.length;i++)
for (int j = 0;j < bitmap[0].length;j++)
bitmap[j] = '.';

}

public static void print_bitmap(char[][] bitmap) {

for (int i = bitmap[0].length - 1;i >= 0;i--) {
for (int j = 0;j < bitmap.length;j++)
System.out.print(bitmap[j]);

System.out.println();
}

}

}[/java]

Why the above code give WA? Is there any special cases the above code cannot take care of?

abc
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm

320 Input plz

Post by abc » Fri Aug 27, 2004 7:31 pm

Post IO plz.. tanx

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Sat Aug 28, 2004 3:31 am

Tell ya what... you post some input, and I'll run it through my newly AC program and share the output with you. Deal? :)
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

p320 - WA, but someone please reply.. :)

Post by dootzky » Fri Apr 22, 2005 11:06 am

i found three other questions about p320, but nobody seems to answer...

anyway, i solved it (at least i think i did), but i keep getting WA.

i hope someone can give me a tip where i'm making a mistake, and i'll put here some sample inputs, which should be good enough for tests.

2
2 1
EEENNNWWWSSS.

2 1
ENWS.

2 1
EEEEEEEEEENWWWWWWWWWWS.

output:

first one should be like a square,
second like ... letter O, more or less,
and third one should be a rectangle.

anyway, here's my code, hopefully someone will test it and tell me where i'm making a mistake. i'm being solving this problem for three months. :oops:
and now i simply must ask for help. :o

my code:

greetzs,
dootzky

Code: Select all


#include <iostream.h>
#include <string.h>
#include <stdio.h>

void main() {

	int i,j,g,p,x,y;
	char a[200],niz[35][35];

	cin >> g;
	for (p=0;p<g;p++) {

	cin >> x >> y;

	y = 31 - y;  // so y would be down in the graph...

	for (i=0;i<32;i++) 
		for (j=0;j<32;j++) niz[i][j]='.';

	gets(a);

	for (j=0;j<(signed)strlen(a)-1;j++) {

		if (a[j]=='E') { 
			niz[y+1][x]='X'; 
			if (a[j+1]=='E') x++;
			if (a[j+1]=='S') {y++; x++;} 
		}

		if (a[j]=='N') { 
			niz[y][x+1]='X'; 
			if (a[j+1]=='N') y--; 
			if (a[j+1]=='E') {y--; x++;}
		}
		
		if (a[j]=='W') { 
			niz[y-1][x]='X'; 
			if (a[j+1]=='W') x--; 
			if (a[j+1]=='N') {y--; x--;}
		}
		
		if (a[j]=='S') { 
			niz[y][x-1]='X'; 
			if (a[j+1]=='S') y++;
			if (a[j+1]=='W') {y++; x--;}
		}


	} // end for j

// write out the graph..
	cout << "Bitmap #" << p+1 << endl;
	// ispis
	for (i=0;i<32;i++) {
		for (j=0;j<32;j++) cout << niz[i][j];
		cout << endl;
	}
	cout << endl;


	} // end for p
}


mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Apr 22, 2005 12:22 pm

It's quite a bad idea to use both C and C++ I/O methods in the same program. Don't use cin or don't use gets().

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Sun Apr 24, 2005 10:34 pm

I didn't check your program but here's the output I get from my AC code:

Input:

Code: Select all

3
2 1
EEENNNWWWSSS.
2 1
ENWS.
2 1
EEEEEEEEEENWWWWWWWWWWS.
Output:

Code: Select all

Bitmap #1
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
..XXX...........................
.X...X..........................
.X...X..........................
.X...X..........................
..XXX...........................

Bitmap #2
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
..X.............................
.X.X............................
..X.............................

Bitmap #3
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
..XXXXXXXXXX....................
.X..........X...................
..XXXXXXXXXX....................


dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

WA WA and more WA

Post by dootzky » Mon Apr 25, 2005 11:47 pm

hi all,

i tryed what MF said, to use SCANF instead of cin, but it still doesn't work. :cry:

then i tryed what sahand said, that is, i tryed his INPUT/OUTPUT cases, and it works on my proggy. :o i mean, perfectly!!

most probably my reading code is wrong, and i would appreciate if someone would post ONLY his "read code", that is how do you take input?

thx for tha' help anyway,
i appreciate it,
dootzky

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Mon Apr 25, 2005 11:52 pm

OK, Here's how I do it:

Code: Select all

int main()
{
	int cases;
	cin>>cases;
	for(int casei=1;casei<=cases;casei++)
	{
		bool bitmap[32][32];
		for(int i=0;i<32;i++)
			for(int j=0;j<32;j++)
			bitmap[i][j]=false;
		
		int x,y;
		cin>>x>>y;
		string line;
		getline(cin,line);
		if(line=="")
			getline(cin,line);

		for(int i=0;i<(int)line.size()-1;i++)
		{
			if(line[i]=='E')
etc....

		}

		cout<<"Bitmap #"<<casei<<endl;
output....
	}
	return 0;
}

hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

320 - Boarder

Post by hiloshi » Tue Apr 26, 2005 11:09 am

I got WA, but I can't make out where is wrong in my code.
This problem looks very easy, and my code actually pass many test cases.
I'm really going to get mad. :evil:
plz help me someone!

Here is my code.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

#define MAX 32

char result[MAX][MAX];
int pre_c = -1;
int x, y;

void init() {
  for(int i = 0 ; i < MAX ; i++) {
    for(int j = 0 ; j < MAX ; j++) {
      result[i][j] = '.';
    }
  }

  pre_c = -1;
}

void func(int c) {
  switch(c) {
  case 0:
    if(pre_c == c) {
      x--;
    } else if(pre_c == 3) {
      x--;
      y--;
    }

    result[y + 1][x] = 'X';
    
    break;
  case 1:
    if(pre_c == c) {
      x++;
    } else if(pre_c == 2) {
      x++;
      y++;
    }

    result[y - 1][x] = 'X';
    
    break;
  case 2:
    if(pre_c == c) {
      y++;
    } else if(pre_c == 0) {
      x--;
      y++;
    }

    result[y][x + 1] = 'X';
    
    break;
  case 3:
    if(pre_c == c) {
      y--;
    } else if(pre_c == 1) {
      x++;
      y--;
    }

    result[y][x - 1] = 'X';
    
    break;
  }

  pre_c = c;
}

void dump(int counter) {
  cout << "Bitmap #" << counter << endl;

  for(int i = MAX - 1 ; i >= 0 ; i--) {
    for(int j = 0 ; j < MAX ; j++) {
      cout << result[i][j];
    }

    cout << endl;
  }

  cout << endl;
}

int main() {
  int n;
  char c;
  int counter = 1;
  string ss;

  cin >> n;

  while(n--) {
    cin >> x >> y;

    init();

    cin >> ss;
    int i = 0;

    while(true) {
      c = ss[i++];

      if(c == '.') {
        dump(counter);

        counter++;

        break;
      }

      switch(c) {
      case 'W':
        func(0);
        break;
      case 'E':
        func(1);
        break;
      case 'N':
        func(2);
        break;
      case 'S':
        func(3);
        break;
      }
    }
  }

  return 0;
}
I hope you can understand my poor English.

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

OMG OMG OMG

Post by dootzky » Thu Apr 28, 2005 11:37 am

hi sahand! i really appriciate you efforts, but i still got WA. :o

i changed my input algo, and it's something like yours (my compiler doesn't recognize "getline(a,200)" ?! it says "unknown getline?!?!". so i use "cin.getline(a,200)", and that works.
bottom line, i tryed all three of your sample inputs in upper part of this post, and my proggy still gives all the correct answers. or at least so it seems (?!).

here is my code again, corrected (although it gives me the same answers in both versions..), and i really hope you can just take it, copy/paste it, and compile it on your machine. maybe there is something really seriously wrong with my compiler (!??!!). i use Visual C++ 6.0.

thank you once again, and i really hope to get ACC in next 15 years or so, :lol: , here's my code:

Code: Select all

#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void main() {

	int i,j,g,p,x,y;
	char niz[35][35],a[200];

	cin >> g;	   
	for (p=0;p<g;p++) {

	cin >> x >> y;

	y = 31 - y;  // this is so i could work with Y on the bottom of
                                 // the graph. so i don't invert the graph. 

	for (i=0;i<32;i++)  // init grafika
		for (j=0;j<32;j++) niz[i][j]='.';

	//gets(a);
	
	// my NEW input...
	cin.getline( a, 200);
    if(strlen(a)==0) cin.getline( a, 200);
         

	for (j=0;j<(signed)strlen(a)-1;j++) {

		if (a[j]=='E') { 
			niz[y+1][x]='X'; 
			if (a[j+1]=='E') x++;
			if (a[j+1]=='S') {y++; x++;} 
		}

		if (a[j]=='N') { 
			niz[y][x+1]='X'; 
			if (a[j+1]=='N') y--; 
			if (a[j+1]=='E') {y--; x++;}
		}
		
		if (a[j]=='W') { 
			niz[y-1][x]='X'; 
			if (a[j+1]=='W') x--; 
			if (a[j+1]=='N') {y--; x--;}
		}
		
		if (a[j]=='S') { 
			niz[y][x-1]='X'; 
			if (a[j+1]=='S') y++;
			if (a[j+1]=='W') {y++; x--;}
		}


	} // end for j

	cout << "Bitmap #" << p+1 << endl;
	// output
	for (i=0;i<32;i++) {
		for (j=0;j<32;j++) cout << niz[i][j];
		cout << endl;
	}
	cout << endl;


	} // end for p

}
thx again,
ReSPeCT,
dootzky

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

Post by dootzky » Thu Apr 28, 2005 11:38 am

one more thing, i noticed that you use STRING line,
but my compiler doesn't allow this. is it because i maybe forgot to #include something?? i includede <string.h>, anything else perhaps??

i use "char a[200]", but the effect is the same.

thx,
d

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Apr 28, 2005 12:35 pm

Input:

Code: Select all

1
3 6
SSSEEENNNWWW.
The output of my accepted program:

Code: Select all

Bitmap #1
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
...XXX..........................
..X...X.........................
..X...X.........................
..X...X.........................
...XXX..........................
................................
................................
Your program printed the image, shifted up by one row.

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Thu Apr 28, 2005 3:08 pm

I checked your code and it seems it's more a problem with your algorithm than the way you treat input.
Hint: Inside this loop:

Code: Select all

for (j=0;j<(signed)strlen(a)-1;j++) {....}
You can accomplish what you want by using only a. There's no need to look ahead.

And also, It's better if you include your files this way:

Code: Select all

#include <iostream> //for cin and cout and streams etc...
#include <string>     //for C++ class std::string
#include <cstdio>    //for C style printf and scanf
#include <cstdlib>   //for C style utility functions
#include <cstring> //for C style string functions such as strlen

using namespace std;//so you don't have to put std:: in front of everything
in this way, you can use something like:

Code: Select all

string line;
getline(cin,line);

Post Reply

Return to “Volume 3 (300-399)”