320 - Border

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

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

chunyi81 · 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 · 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 · Post by **abc** » Fri Aug 27, 2004 7:31 pm

Post IO plz.. tanx

GreenPenInc · 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?

dootzky · 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.

and now i simply must ask for help.

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 · 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().

sahand · 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 · 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.

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

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

sahand · 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 · 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.

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;
}

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

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

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,

, 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 · 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 · 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.

sahand · 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);

OJ Board

320 - Border

Why 320 WA

320 - Border

320 Input plz

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

WA WA and more WA

320 - Boarder

OMG OMG OMG