320 - Border
Moderator: Board moderators
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
Why 320 WA
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.
[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
[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?
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?
-
- Learning poster
- Posts: 53
- Joined: Sat May 01, 2004 9:31 pm
- Contact:
-
- New poster
- Posts: 36
- Joined: Tue Apr 12, 2005 12:20 am
- Location: belgrade, serbia (ex yugoslavia)
- Contact:
p320 - WA, but someone please reply.. :)
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
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
}
-
- New poster
- Posts: 19
- Joined: Sat Mar 12, 2005 5:56 pm
- Location: Halifax, Nova Scotia, Canada
- Contact:
I didn't check your program but here's the output I get from my AC code:
Input:
Output:
Input:
Code: Select all
3
2 1
EEENNNWWWSSS.
2 1
ENWS.
2 1
EEEEEEEEEENWWWWWWWWWWS.
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....................
-
- New poster
- Posts: 36
- Joined: Tue Apr 12, 2005 12:20 am
- Location: belgrade, serbia (ex yugoslavia)
- Contact:
WA WA and more WA
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
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.

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
-
- New poster
- Posts: 19
- Joined: Sat Mar 12, 2005 5:56 pm
- Location: Halifax, Nova Scotia, Canada
- Contact:
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
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.
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;
}
I hope you can understand my poor English.
-
- New poster
- Posts: 36
- Joined: Tue Apr 12, 2005 12:20 am
- Location: belgrade, serbia (ex yugoslavia)
- Contact:
OMG OMG OMG
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:
thx again,
ReSPeCT,
dootzky

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,

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
}
ReSPeCT,
dootzky
Input:
The output of my accepted program:
Your program printed the image, shifted up by one row.
Code: Select all
1
3 6
SSSEEENNNWWW.
Code: Select all
Bitmap #1
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
...XXX..........................
..X...X.........................
..X...X.........................
..X...X.........................
...XXX..........................
................................
................................
-
- New poster
- Posts: 19
- Joined: Sat Mar 12, 2005 5:56 pm
- Location: Halifax, Nova Scotia, Canada
- Contact:
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:
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:
in this way, you can use something like:
Hint: Inside this loop:
Code: Select all
for (j=0;j<(signed)strlen(a)-1;j++) {....}
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
Code: Select all
string line;
getline(cin,line);