Help-2 dimensional array

Discussion in 'Computer Science & Culture' started by ksar22, Apr 22, 2002.

Thread Status:
Not open for further replies.
  1. ksar22 Registered Member

    Messages:
    2
    hi,
    can anyone help me with this
    i have no clue
    I have to write an algorithm that will search a two dimensional array for ships. The array will be a char array initialized with two character values-the value '~' to represent water, and the value 'x' to represent a square occupied by a ship.The code below initializes an array that represents the grid in the diagram. It contains five ships.

    const int Size = 6;
    char ocean[Size][Size] = {
    {‘~’, ‘~’, ‘x’, ‘x’, ‘~’, ‘x’},
    {‘x’, ‘~’, ‘~’, ‘~’, ‘~’, ‘x’},
    {‘x’, ‘~’, ‘x’, ‘x’, ‘~’, ‘x’},
    {‘x’, ‘~’, ‘~’, ‘~’, ‘~’, ‘x’},
    {‘~’, ‘~’, ‘~’, ‘~’, ‘~’, ‘~’},
    {‘~’, ‘x’, ‘x’, ‘x’, ‘x’, ‘~’},
    };

    It should print a sentence for each ship it finds. The output should contain the length of the ship.

    a.out
    Found a ship, its length is 2.
    Found a ship, its length is 4.
    Found a ship, its length is 3.
    Found a ship, its length is 2.
    Found a ship, its length is 4.

    In advance thanks a lot for your assistance
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Adam §Þ@ç€ MØnk€¥ Registered Senior Member

    Messages:
    7,415
    I did the same code in a game of Tic Tac Toe, but it was sort of crappy. I think I'd better leave it to more experienced programmers.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. sjmarsha Registered Senior Member

    Messages:
    363
    Not sure i fI am more experienced but...

    I would have a for loop cycling across the array (horizontally) and then moving onto the next line.

    If you find an x check to see if the next char is also a x, If it is then increment another counter until you don't find an x. Then print out the results.

    If the next one isn't an x check the char immediatly below it. Again if it is an x keep going until you don't find a x. Print out the results.

    In addition to the above you would also have to check whether you are falling off your array.
    AND,
    To stop you from finding ships multiple times I would look above/to the left of the first x to make sure that you are at the beginning of the ship.

    Hope that helps.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Adam §Þ@ç€ MØnk€¥ Registered Senior Member

    Messages:
    7,415
    so it increments through and then you have something in the loop like:

    if(array[counter] == 'x')
    startposition = array[counter];

    and on subsequent loops you test for whether there is an 'x' at startposition+1 or at startposition+6 (or plus whatever gets it to directly below the startposition).

    Then you've got two places. Those two positions are stored as a shipposition, and you loop once again to see if their is an 'x' at startposition+1 or startpositiont+6. Hell, you don't even have to loop. Once you have the first position, you can just query those two locations in the array. But if you don't get a ship in your queries, then maybe continue looping through the array to search.
     
  8. sjmarsha Registered Senior Member

    Messages:
    363
    I didn't fully understand what you said but... you have the basics.

    You have to loop round in this order...

    1 2 3 4 5 6
    7 8 9 10 11 12
    13 14 15 16 17 18
    etc

    because you have to find all ships. Now either to stop multiple hits you could do one of the following.

    1)expand the array to become 3d, so for each position you have a variable called ship or something. If a x has been found there already you just ignore it the second time you find it.

    2)Store the positions of the ships in another array. (Could be difficult to code)

    3)Check to see if you are at the start of the ship. If not then ignore it.

    I.E. In the original example there is a x in position 3. So when you have looped around and found this, your code should check the position in the array before this (2 in our example) and the position above it (off the array in our example). If these come back negative then you know that you have a new ship. ( you would then have to increment a ship length counter)
    Then you check the length of the ship. So you check the position after it (4 in our example). If there is a ship (which there is) you increment the counter and repeat.
    If there isn't then you check the position imediatly below it (9 in our example) to see if the ship is aligned vertically.

    Clear?? I don't really understand what I wrote so I can't expect you too. I would put a full code listing in, but I think this sounds like an assignment question. If you are interrested Adam I could have a go at coding it tommorrow....
     
  9. ksar22 Registered Member

    Messages:
    2
    hi guys,
    i greatly appreciate for your solutions
    you really helped me
    thanks a lot
     
  10. Adam §Þ@ç€ MØnk€¥ Registered Senior Member

    Messages:
    7,415
    Just messing around with ideas, I don't really know what I'm doing here. I'm still not the best with pointers. But it seems to me that at least we can be sure a ship will be no more than 6 chars long, now gotta run through each level of the array. I dunno.

    int main(int argc, char *argv[])
    {

    char ocean[6][6] = {
    {'~', '~', 'x', 'x', '~', 'x'},
    {'x', '~', '~', '~', '~', 'x'},
    {'x', '~', 'x', 'x', '~', 'x'},
    {'x', '~', '~', '~', '~', 'x'},
    {'~', '~', '~', '~', '~', '~'},
    {'~', 'x', 'x', 'x', 'x', '~'}
    }
    int *ptr = ocean[0][0], foundship[6], i = 0;

    while(ptr < 6)
    {
    if(ptr == 'x')
    foundship = ptr;
    ptr++;
    }
     
  11. sjmarsha Registered Senior Member

    Messages:
    363
    I haven't the time to finish it off anymore so I am afraid you are all on your own.
     
  12. Ash711 Registered Member

    Messages:
    24
    maybe.....

    hi everyone,

    I just thought of this, tell me what you think plz:

    create a array of integer[6] that will store the number of 'x' above the line you look at, lets call it lineCop
    At the beginning of the prog, i'll assume that lineCop is clear (ie set to 0)

    You visit the ocean array incrementally, ie line per line, then col per col

    Each time you fell on a 'x' at pos 6*i+j (the i line and col j) you increment lineCop[j]
    Each time you fell on '~' at pos 6*l+k you
    *Read the value of lineCop[k], if it is > to 1 then you found a vertical ship of lenght lineCop[k], output and clear it (the value)
    *If <1, then clear it to 0;

    To check for horizontal ship, you use the same technique, except that you don't need an array, just a scalar that will store the number of 'x' found before and that will be cleared each time you find '~'

    cia soon
     
  13. Rick Valued Senior Member

    Messages:
    3,336
    Gee...

    i am bored...

    Please Register or Log in to view the hidden image!





    bye!
     
  14. Rick Valued Senior Member

    Messages:
    3,336
    has anyone tried their hands with TSRs?

    OR
    building GUIs,mouse programming,buiding different cursors(mouse)
    other interesting stuffs like graphics...

    Please Register or Log in to view the hidden image!





    bye!
     
  15. Ash711 Registered Member

    Messages:
    24
    sorrrrrry

    couldn't resist

    Please Register or Log in to view the hidden image!




    see joined file
    it is c++

    if you want c, simply replace cout with printf, and replace the first include
    hopes that helps
     
  16. Deus Seeker of Truth Registered Senior Member

    Messages:
    65
    I'm working on programming in Qt, which is a GUI library for C++. So far it's pretty nice, although you have to spend some time learning it, it's not quite as easy as Visual Basic, but it's more powerful. You can get Qt for free, but any program you generate with the free version must be released as freeware and there is a little [Freeware] thing in the title bar of the main application all the time.

    http://www.trolltech.com if you're interested.
     
  17. Rick Valued Senior Member

    Messages:
    3,336
    Dont get me wrong(FOR MY BOASTING part of it),
    we C,C++ programmers cannot be compared with those VB proffessionals out there.so i know how tough it is to build GUI.i have build a lot of stuff on this.(Like for example i had built a GUI based program which gives info on U.S.A.)
    states,connected routes etc...

    believe me with that Linerel() function i had to spend almost a month to get every details correct,like plotting the whole map on graph paper,taking it pixel by pixel.but when completed it was great,a true masterpiece.Thats what i like about programming,you feel like GOD,you feel like Michael Angelo you know.


    the Menus itself requires lots of accuracy,like you have to set delay() function with great care so as to match the delay time.

    i posted because i wanted to share my TSR and graphics in C experience with someone...

    PS:I AM CURRENTLY BUILDING THE NOTEDPAD,WITH GUIS etc.it gets activated with F10 key pressed.and has all the modern times editors features....


    bye!
     
  18. Rick Valued Senior Member

    Messages:
    3,336
    here's some code for command buffer TSR.

    compile and check it out as *.exe,its cool...
    /*COMMAND BUFFER*/
    #pragma inline
    #include"dos.h"
    #include"stdio.h"
    #include"conio.h"
    #include"bios.h"
    #define ENTER 13
    #define ESCAPE 27
    #define BACKSPACE 8
    #define TAB 9
    #define UP_ARROW 72
    #define DOWN_ARROW 80
    #define LEFT_ARROW 75
    #define F7 65
    #define STACKSIZE 512

    struct INTERRUPT
    {
    unsigned bp,di,ds,es,dx,cx,bx,ax,ip,cs,fl;
    };
    union REGS i,o;
    void interrupt (*prev)();
    void interrupt our(struct INTERRUPT);
    unsigned char far *buffer,string[128];
    char far *scr=(char far *)0xB8000000L;
    char stk[STACKSIZE],row,col,startrow,startcol,ascii,scan;
    int maxlen,stk_count,count,prev_count,j,brk_flag,tab,end,remove();

    void main()
    {
    prev=getvect(0x21);//DOS...
    setvect(0x21,our);
    keep(0,1000);
    }
    void interrupt our()
    {
    if(_AH==0x0A)
    {
    enable();
    count=0;
    brk_flag=0;

    //GET CURSOR POSITION
    buffer=MK_FP(_DS,_DX);//DS

    Please Register or Log in to view the hidden image!

    X address of buffer
    //save maximum length of the command
    maxlen=*buffer;

    //read command until enter is ressed
    while(!brk_flag)
    {
    getkey();
    switch(ascii)
    {
    case 0:
    if(stk_count==0)
    continue;
    switch(scan)
    {
    case UP_ARROW:
    up();
    break;
    case DOWN_ARROW:
    down();
    break;
    case LEFT_ARROW:
    backspace();
    break;
    case F7:
    escape();
    printstack();
    }
    break;
    case ENTER:
    enter();
    break;
    case ESCAPE:
    escape();
    break;
    case BACKSPACE:
    backspace();
    break;
    case TAB:
    puttab();
    break;
    default:
    if(count==(maxlen-1))
    continue;

    *(buffer+2+count)=ascii;

    //DISPLAY CHARRACTER AT CURSOR
    writechar(ascii,row,col);
    count++;
    col++;
    checkcol();
    setxy(col);
    }
    }
    /*SET NUMBER OF CHARRACTERS ACTUALLY READ...
    EXCLUDING CARRIAGE RETURN*/
    *(buffer+1)=count;

    _AX = _AX&0xf0;//set al=0
    return;
    }
    //pop values back from stack into registers.
    asm pop bp
    asm pop di
    asm pop si
    asm pop ds
    asm pop es
    asm pop dx
    asm pop cx
    asm pop bx
    asm pop ax
    /*transfer control to NORMAL DOS ROUTINES...*/
    asm jmp cs

    Please Register or Log in to view the hidden image!

    rev
    }

    //funtions defined...
    setxy(int col)
    {
    //position cursor
    i.h.ah=2;//service routine
    i.h.bh=0;
    i.h.dh=row;
    i.h.dl=col;
    int86(0x10,&i,&o);
    }
    getkey()
    {
    //wait as long as key is not hit
    while(!kbhit())
    ;
    i.h.ah=0x00;
    int86(0x16,&i,&o);
    /*the above function defines interrupt 16h */
    scan=o.h.ah;
    ascii=o.h.al;
    }

    //for writing charracters on VDU
    writechar(char ch,int r,int c)
    {
    ch = *(scr + r*160 + c*2);
    }
    clearrow()
    {
    row=startrow;
    col=startcol;
    for(j=0;j<count;j++)
    writechar(' ',row,startcol+j);

    setxy(col);
    }
    backspace()
    {
    //if cursor is at begining of the command
    if(col==startcol&&row==startrow)
    return;
    col--;

    //if multiple line command and cursor is
    //at the begining of the
    //second line
    if(col<0)
    {
    col=79;
    row--;
    }
    count--;
    writechar(' ',row,col);

    setxy(col);
    }
    //DETERMINE THE NEXT
    //TAB STOP
    puttab()
    {
    tab=(8-col%8);
    //MOVE THE CURSOR TO NEXT TAB STOP
    col+=tab;
    setxy(col);
    for(j=0;j<tab;j++)
    {
    *(buffer+2+count)=' ';
    count++;
    }
    }
    scrollup()
    {
    i.h.ah=6;
    //service routine number
    i.h.al=1;
    //lines to scroll up
    i.h.bh=7;
    //filler attribute
    i.h.ch=0;
    //UPPER ROW
    i.h.cl=0;
    //left column
    i.h.dh=24;
    //lower row
    i.h.dl=79;
    //right column

    int86(0x10,&i,&o);
    }
    //cursor position tracer
    getcursorposition()
    {
    i.h.ah=3;
    i.h.bh=0;
    int86(0x10,&i,&o);

    startrow=row=o.h.dh;
    startcol=col=o.h.dl;
    }
    up()
    {
    clearrow();
    //clears the current row

    //go to the begining of the
    //previous command
    //if already at first command,go beyond the '\r' of
    //the last command
    if(prev_count==0)
    prev_count=stk_count;
    prev_count-=2;


    while(stk[prev_count]!=ENTER && prev_count!=0)
    prev_count--;
    if(prev_count!=0)
    prev_count++;

    //DISPLAY COMMAND
    col=startcol;
    count=0;
    while(stk[prev_count+count]!=ENTER)
    {
    //display the charracter at cursor
    //position
    writechar(stk[prev_count+count],row,col)

    //place the charracter in buffer

    *(buffer+2+count)=stk[prev_count+count];
    count++;
    col++;
    checkcol();
    setxy(col);
    }
    }
    down()
    {
    //clear the current row
    clearrow();

    //go to begining of the next command
    if(prev_count!=stk_count)
    {
    while(stk[prev_count]!=ENTER && prev_count!=stk_count)
    prev_count++;

    prev_count++;
    }

    //if end of the stack is reached...
    //go to the begining of the command,first one...
    if(prev_count==stk_count)
    prev_count=0;

    //DISPLAY COMMAND
    col=startcol;
    count=0;
    while(stk[prev_count+count]!=ENTER)
    {
    //DISPLAY THE CHARRACTER AT CURRENT CURSOR POSITION
    writechar(stk[prev_count+count],row,col)

    //PLACE THE CHARRACTER IN THE BUFFER
    *(buffer+2+count)=stk[prev_count+count];
    count++;
    col++;
    checkcol();
    setxy(col);
    }
    }
    enter()
    {
    *(buffer+2+count)=ascii;

    //if it is not a NULL command
    if(count<0)
    {
    //if enough spae is not available
    if(stk_count+count>=STACKSIZE-1)
    {
    //remove no. of command
    remove=(stk_count+count)-STACKSIZE-2;

    j=0;
    while(j<remove)
    {
    while(stk[j]!=ENTER)
    j++;
    j++;
    }
    //store the current command on
    //stack from the buffer
    for(j=0;j<=count;j++)
    {
    stk[stk_count]=*(buffer+2+j);
    stk_count++;
    }
    }
    prev_count=stk_count;
    brk_flag=1;
    }

    escape()
    {
    //WIPE OUT A DOS COMMAND
    clearrow();
    count=0;
    }
    checkcol()
    {
    if(col<80)
    {
    row++;
    if(row==25)
    {
    startrow--;
    row--;
    scrollup();
    }

    col=(col-80);
    }
    }
    //display commands stored in stack
    printstack()
    {
    if(++row==25)
    {
    row--;
    scrollup();
    }
    col=0;
    for(j=0;j<stk_count;j++)
    {
    if(stk[j]==ENTER)
    {
    if(++row==25)
    {
    row--;
    scrollup();
    }
    col=0;
    }
    else
    [
    writechar(stk[j],row,col++)
    checkcol();
    }
    setxy(col);
    }
    *(buffer+2+count)=ENTER;
    brk_flag=1;
    }




    bye!
    ENJOY and have fun.
     
  19. Rick Valued Senior Member

    Messages:
    3,336
    hahahahahahahhaha...
    take a look at CS : PREV instruction asm part.
    ahahhahahahahaha...



    bye!
     
Thread Status:
Not open for further replies.

Share This Page