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

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

Post by dootzky » Fri Apr 29, 2005 1:40 am

oh, i see what you mean. :-?

my algorithm is obviously wrong. :roll:

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! 8)

thanx guys, i'll try to think of better way of mapping my path.
... no need to look ahead, eh? :o interesting. i'll think about it.

cheers guys,
dootzky

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

Post by dootzky » Fri Apr 29, 2005 11:55 am

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 :D

if (a[0]=='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. :cry:

Code: Select all

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

void main() {

	int i,j,g,p,x,y;
	char niz[35][35],a[200],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[0]=='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:

Post by mf » Fri Apr 29, 2005 1:22 pm

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
Location: belgrade, serbia (ex yugoslavia)
Contact:

Post by dootzky » Fri Apr 29, 2005 11:08 pm

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.) :D

i really don't get it.
am i so desperate that i can't solve one problem?! which even isn't so complicated?! :oops: :-?
i solved 88 problems, and many of them were hard, or confusing, but this one is becoming irritating... :evil: seriously.

anyway, i appreciate any help i can get, and i know i won't stop untill i get ACC, so.. HEEEELP ME! haha... :D

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[32][32]), 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:

Post by mf » Sat Apr 30, 2005 10:44 am

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[32][32]), 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
Location: belgrade, serbia (ex yugoslavia)
Contact:

OMG OMG OMG!!

Post by dootzky » Sat Apr 30, 2005 3:49 pm

I GOT ACCEPTED!! After ONLY 48 attempts!!

this was... oh.. my..god... problem. OMG! :o haha..
but seriously, thank you, everybody, for you help.
i changed the Y axis direction, and reversed it back to normal (like you, MF) :D,
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. :wink:
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. :roll:
best regards,
dootzky

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

Plzzzz

Post by hiloshi » Wed Jul 27, 2005 2:50 pm

Please help me.
I really confuse.
I hope you can understand my poor English.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv » Mon Aug 08, 2005 2:25 pm

The var pre_c is not needed.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Apr 04, 2006 4:01 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

Post by mars kaseijin » Thu Sep 25, 2008 10:45 am

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[32][32];
    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);
}



Post Reply

Return to “Volume 3 (300-399)”