Page 1 of 2

Posted: Thu Apr 10, 2003 4:35 am
by Red Scorpion
Hi,
No Trick at all. Just do what they want.

Why 320 WA

Posted: Sat Jul 05, 2003 5:26 am
by chunyi81
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.

320 - Border

Posted: Mon Jul 07, 2003 6:11 am
by chunyi81
[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?

320 Input plz

Posted: Fri Aug 27, 2004 7:31 pm
by abc
Post IO plz.. tanx

Posted: Sat Aug 28, 2004 3:31 am
by GreenPenInc
Tell ya what... you post some input, and I'll run it through my newly AC program and share the output with you. Deal? :)

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

Posted: Fri Apr 22, 2005 11:06 am
by dootzky
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
}


Posted: Fri Apr 22, 2005 12:22 pm
by mf
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().

Posted: Sun Apr 24, 2005 10:34 pm
by sahand
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....................


WA WA and more WA

Posted: Mon Apr 25, 2005 11:47 pm
by dootzky
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

Posted: Mon Apr 25, 2005 11:52 pm
by sahand
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;
}

320 - Boarder

Posted: Tue Apr 26, 2005 11:09 am
by hiloshi
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;
}

OMG OMG OMG

Posted: Thu Apr 28, 2005 11:37 am
by dootzky
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

Posted: Thu Apr 28, 2005 11:38 am
by dootzky
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

Posted: Thu Apr 28, 2005 12:35 pm
by mf
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.

Posted: Thu Apr 28, 2005 3:08 pm
by sahand
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);