Thread: A recursive problem?

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    26

    A recursive problem?

    Hey guys,

    I have a 2 dimension 8 by 8 array which is fill with "." and 2 Xs. I need to find the shortest possible path from one X to another X recursivley. Can anyone help me to find the solution please? Thanks in advance. Here is the array which i've:

    Code:
    char grid[][8] = { 
                 {'.','.','.','.','.','.','.','.'}, 
                 {'.','.','.','.','.','.','.','.'}, 
                 {'.','.','.','.','.','.','.','.'}, 
                 {'.','.','.','X','.','.','.','.'}, 
                 {'.','.','.','.','.','.','.','.'}, 
                 {'.','.','.','.','.','X','.','.'}, 
                 {'.','.','.','.','.','.','.','.'}, 
                 {'.','.','.','.','.','.','.','.'}  
        };

  2. #2
    ^ Read Backwards^
    Join Date
    Sep 2005
    Location
    Earth
    Posts
    282
    What exactly do you mean by shortest possible path from one x to another x?

  3. #3
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215
    the shortest possible path would be a line, look up some line algorithms on google
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

  4. #4
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215
    You could translate this algorithm to use recursion. Its called the bresenham algorithm, made for drawing effective lines between 2 pixels quickly:

    Code:
    void brenenham1(int x1, int y1, int x2, int y2)
    {
        int slope;
        int dx, dy, incE, incNE, d, x, y;
    
        // Reverse lines where x1 > x2
        if (x1 > x2)
        {
            bresenham1(x2, y2, x1, y1);
            return;
        }
    
        dx = x2 - x1;
        dy = y2 - y1;
    
        // Adjust y-increment for negatively sloped lines
        if (dy < 0)
        {
            slope = -1;
            dy = -dy;
        }
        else
        {
            slope = 1;
        }
    
        // Bresenham constants
        incE = 2 * dy;
        incNE = 2 * dy - 2 * dx;
        d = 2 * dy - dx;
        y = y1;
    
        // Blit
        for (x = x1; x <= x2; x++)
        {
            putpixel(x, y);
            if (d <= 0)
            {
                d += incE;
            }
            else
            {
                d += incNE;
                y += slope;
            }
        }
    }
    EDIT:
    if all else fails, you could modify the array to hold a struct and apply the bellman-ford algorith to it. It's made for picking the shortest possible path throughout a whole bunch of nodes. It's used fo routing data throughout large networks such as the internet . A good way to impress your professor nonetheless.
    Last edited by durban; 10-31-2005 at 06:24 PM.
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

  5. #5
    Registered User
    Join Date
    Jul 2005
    Posts
    26
    Quote Originally Posted by Enahs
    What exactly do you mean by shortest possible path from one x to another x?
    Can't you display the whole array and kind of path with other letter for example "P" from one X to another X?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Problem.
    By penance in forum C Programming
    Replies: 4
    Last Post: 07-07-2005, 10:16 AM
  2. recursive function problem
    By jk81 in forum C Programming
    Replies: 2
    Last Post: 10-25-2002, 06:02 AM
  3. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM
  4. Problem with a recursive function
    By fofone in forum C Programming
    Replies: 2
    Last Post: 03-07-2002, 08:21 AM
  5. Recursive problem...
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2002, 04:20 PM