## 320 - Border

Moderator: Board moderators

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:
oh, i see what you mean. my algorithm is obviously wrong. thank you, mf, for sample input, i will consider it for my future algo,
and thank you, sahand, for all the comments. i will try to implement them in my future work.

i'll call this a day, and tomorrow i'm gonna solve this problem, even if i don't get of the chair all day! thanx guys, i'll try to think of better way of mapping my path.
... no need to look ahead, eh? interesting. i'll think about it.

cheers guys,
dootzky

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:
guys, i did something like this:

i didn't look in forward character, but instead i simply memorized which character was the last one.

even so, sample inputs are generaly ok, but input from MF is STILL one row shifted up?!?! (omg omg omg)
but then i added this one line, just to correct that if (a=='S') y++; (so my graph would start lower than normal..)

i don't know if i should maybe add something like this for other directions?

here is my 'corrected' code, but ofcourse, it's still WA. Code: Select all

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

void main() {

int i,j,g,p,x,y;
char niz,a,last;

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

cin >> x >> y;

y = 31 - y;  // da bi prebacili y na donji deo grafika...

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

last = 'z';
// ############# :) ##############
//if (a=='S') y++; // HAAAAR HAR HAR ... :)

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

if (a[j]=='E') {
if (last=='E') x++;
else if (last=='N') { x++; y--; }

niz[y+1][x]='X';
last = 'E';

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

if (a[j]=='N') {
if (last=='N') y--;
else if (last=='W') { x--; y--; }

niz[y][x+1]='X';
last = 'N';

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

if (a[j]=='W') {
if (last=='W') x--;
else if (last=='S') { x--; y++; }

niz[y-1][x]='X';
last = 'W';

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

if (a[j]=='S') {
if (last=='S') y++;
else if (last=='E') { x++; y++; }

niz[y][x-1]='X';
last = '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;

} // kraj glavnog for p

}
``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try to make a simpler algorithm. There's really no need ever to look back or forward, or have any special cases.

Note that the point is said to be moving counter-clockwise. This basically means, that the border always lies to the right of the point's path.

For example, in the 'S' command, the point moves from (x,y) to (x,y-1), and the border is always a "box" whose right side is the segment ((x,y) - (x,y-1)), regardless of what the other commands are.

Just try to do some drawings on the paper, hope you'll get the idea.

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:
omg.

i did so much writing today, that my hand is gonna fall-off!
and still, the BEST possible and most simple algo i found is this:

Code: Select all

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

if (a[j]=='N') { niz[y--][x]='X'; }

if (a[j]=='W') { niz[y][--x]='X'; }

if (a[j]=='S') { niz[++y][x-1]='X'; }
``````
is it correct?! it gives me all the right answers, even for MF sample input (1, 3 6, SSSEEENNNWWW.) i really don't get it.
am i so desperate that i can't solve one problem?! which even isn't so complicated?!  i solved 88 problems, and many of them were hard, or confusing, but this one is becoming irritating... seriously.

anyway, i appreciate any help i can get, and i know i won't stop untill i get ACC, so.. HEEEELP ME! haha... one more thing, MF, you said:
"....and the border is always a "box" whose right side is the segment ((x,y) - (x,y-1)).... "

i don't get it - what exactly is the 'segment' ? by "box" i guess you mean one character place in my 2D array (char), but what is "segment ((x,y) - (x,y-1)) " ?

cheers,
i gotta go get some sleep,
dootzky

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
My algorithm is exactly like yours, except that I preferred not to change the direction of y-axis.
If your program doesn't get accepted, maybe it's again some problem with I/O code.
My program uses scanf("%d", ...) to read integers, and getchar() to read the path's description.
one more thing, MF, you said:
"....and the border is always a "box" whose right side is the segment ((x,y) - (x,y-1)).... "

i don't get it - what exactly is the 'segment' ? by "box" i guess you mean one character place in my 2D array (char), but what is "segment ((x,y) - (x,y-1)) " ?
I referred to the mathematical coordinate system, which is shown in the problem's statement. By the box I meant the square with corners at the points (x,y), (x,y-1), (x-1,y-1), (x-1,y). When the point moves from (x,y) down to (x,y-1), this square is always part of the border. And thus, the program should put 'X' in the array's cell, which corresponds to it. It depends on the programmer, what exactly the array represents, after all.

A "segment ((x,y) - (x,y-1))" is just a straight line, joining the points (x,y) and (x,y-1). It's quite a standard geometric term, I think.

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:

### OMG OMG OMG!!

I GOT ACCEPTED!! After ONLY 48 attempts!!

this was... oh.. my..god... problem. OMG! haha..
but seriously, thank you, everybody, for you help.
i changed the Y axis direction, and reversed it back to normal (like you, MF) ,
and besides that, input was, AGAIN, big big problem.

finaly, i used THIS code for input:

Code: Select all

``````scanf ("%d",&g); // for reading number of test cases
scanf ("%d%d\n",&x,&y); // for reading starting coordinates
gets(a);  // for reading the whole line of commands.
``````
please note that for the first number, i don't read "%d \n", and for second pair of numbers i MUST use "%d%d\n", or it wont work.
that was the catch? OMG. that was the reason (besides of my bad algo) i got 48 WA? i mean... really..

phuh. glad THAT was done, now i can solve other problem. yey. i just hope i won't get THIS stuck ever ever again, with any problem.

thx one more, MF and sahand, i couldn't do it without you help. best regards,
dootzky

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

### Plzzzz

I really confuse.
I hope you can understand my poor English.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
The var pre_c is not needed.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I know it's a bit (heh) late, but the line can be longer than 255 characters. And you should print a blank line after the last case.

Maybe you want to remove the code.

Darko

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

### Re: Why 320 WA

I did 320 for the fun of it. The output is unexpected. Compile and take a look for yourself.

Code: Select all

``````//
// File:   newmain.cc
// Author: Vaio
//
// Created on September 17, 2008, 7:32 PM
// There is a difference between points and squares but the diagram is plain
// wrong.

#include <iostream>
#include <string>
#include <sstream>
#include <limits>

using namespace std;

enum { north, east, south, west };

struct Point
{
int x, y;

Point() : x(0), y(0) { }

Point(int xx, int yy) : x(xx), y(yy) { }

Point(const Point& p) : x(p.x), y(p.y) { }

friend ostream& operator<<(ostream& o, const Point& p)
{
return o << "[" << p.x << "," << p.y << "]";
}

Point& go(const int i)
{
switch(i)
{
case west:  x--; break;
case east:  x++; break;
case north: y++; break;
case south: y--; break;
}
return *this;
}
};

struct Square
{
bool n, e, s, w;

Square() { n = e = s = w = false; }

bool isEmpty() const
{
if(!n && !e && !s && !w) return true;
return false;
}

friend ostream& operator<<(ostream& o, const Square& s)
{
return o << boolalpha << s.n << " : " << s.e << " : " << s.s << " : " << s.w;
}
};

class Bitmap
{
private:
Square sq;
Point begin;
string inputs;

public:
Bitmap(const Point& p) : begin(p) { }

void draw()
{
Point cur(begin);

for(string::iterator it = inputs.begin(); it != inputs.end(); it++)
{
char ch = *it;
Point rhs(cur);
Point origin;
sq[origin.y][origin.x].n = true;    // the origin.

if(ch == '.') break;
switch(ch)
{
case 'N':
rhs.x++;
sq[rhs.y][rhs.x].w = true;
cur = cur.go(north);
break;
case 'E':
rhs.y--;
sq[rhs.y][rhs.x].n = true;
cur = cur.go(east);
break;
case 'W':
rhs.y++;
sq[rhs.y][rhs.x].s = true;
cur = cur.go(west);
break;
case 'S':
rhs.x--;
sq[rhs.y][rhs.x].e = true;
cur = cur.go(south);
break;
}
#ifdef DEBUG
cout << "cur: " << cur << '\t' << "rhs: " << rhs << endl;
#endif
}
}

friend ostream& operator<<(ostream& o, const Bitmap& b)
{
for(int y = 31; y >= 0; y--)
{
o << endl;
for(int x = 0; x < 32; x++)
{
if(b.sq[y][x].isEmpty()) o << '.';
else if(y == 0 && x == 0) o << 'O'; // bearing check
else o << 'X';
}
}
return o;
}

friend istream& operator>>(istream& i, Bitmap& b)
{
return i >> b.inputs;
}
};

int main(int argc, char** argv) {
int n;
cin >> n;   // Check for numeric limits!
numeric_limits<int> lim;
if(n >= lim.max())
{
cerr << endl << "The monkey wrench! Argh!!!" << endl;
return 1;
}

for(int i = 0; i < n; i++)
{
cout << endl << "Bitmap #" << i+1 << endl;
int startx, starty;
cin >> startx >> starty;
Point p(startx, starty);
Bitmap bt(p);
cin >> bt;

bt.draw();

cout << bt << endl;
}

return (EXIT_SUCCESS);
}

``````