BFS Cascading Numbers

closed account (Eh5iz8AR)
Hey guys, first time posting to this site. Just to forewarn you, this is a homework question but i'm not looking for a solution, simply a push in the right direction.

The problem deals with a Breadth First Search on a hexagonal grid, where I have a 22x22 2D array that will determine the shortest path between the two points of Duck Dodgers and Marvin Martian. The grid consists of -1's -2's and the goal which is a 0.

The -1's are empty spaces you can move to, -2's are lava which you can't move to, and the 0 is the goal called Illudium Phosdex.

The part where I am having trouble is when I need to start at the goal (0) and cascade numbers around its 6 neighbors by +1 each time. This picture is the 20x20 grid and an example on what I need to do with it.

http://i.imgur.com/chYI4.png

To get an idea why I need to do this, while using a breadth first search function called findPath I am starting at either Duck Dodgers or Marvin Martian, processNeighbors, and taking their (current path - 1) and enqueueing it to my Queue q. It will keep doing processNeighbor and enqueueing a closer number until the path is reached. I don't know how to do this part and would really appreciate some help.

Heres my queue.cc:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include "queue.h"
#include <iostream>

using namespace std;

const int ROW = 22;
const int COL = 22;
int numberCells(int r, int c);

int map[ROW][COL];

int main(void) {

  int duckX, duckY, marvinX, marvinY, illudiumX, illudiumY, lavaX, lavaY;
  int r,c,nLava;

  for (r=0; r<ROW; r++)
    for (c=0; c<COL; c++)
        map[r][c] = -1;

  for (r=0;r<ROW;r++)
    map[0][r] = map[r][0] = map[ROW-1][r] = map[r][ROW-1] = -2;

  cout << "Please enter Duck Dodger's Y coordinate: ";
  cin >> duckY;
  cout << "Please enter Duck Dodger's X coordinate: ";
  cin >> duckX;
  cout << "\nPlease enter Marvin the Martian's Y coordinate: ";
  cin >> marvinY;
  cout << "Please enter Marvin the Martian's X coordinate: ";
  cin >> marvinX;
  cout << "\nPlease enter the Illudium Phosdex's Y coordinate: ";
  cin >> illudiumY;
  cout << "Please enter the Illudium Phosdex's X coordinate: ";
  cin >> illudiumX;

  illudiumX++;
  illudiumY++;
  duckX++;
  duckY++;
  marvinX++;
  marvinY++;
  // check for validity here if you want

  cout << "Enter number of lava locations: ";
  cin >> nLava;
  for (int i=0;i<nLava;i++) {
    cout << "Enter lava Y location: ";
    cin >> lavaY;
    cout << "Enter lava X location: ";
    cin >> lavaX;
    lavaX++;
    lavaY++;
    // mark lava location
    map[lavaY][lavaX] = -2;
  }

  map[illudiumY][illudiumX] = 0;

  for (r=0; r<ROW; r++) {
  for (c=0; c<COL; c++)
        cout << map[r][c];
        cout << "\n";
  }
//  numberCells(r,c);
system("PAUSE");
}

  // next... find a path for Duck Dodgers and Marvin Martian
  void findPath() {

//Start at one's location, enqueue it. Look at the surrounding neighbors and for any that are (Current Path -1), enqueue them.

  }

  int numberCells(int r, int c) {
//  for (map[illudiumY][illudiumX]) {
    r = r+1; r++;
    c = c+1; c++;
    for (r=0; r<ROW; r++) {
    for (c=0; c<COL; c++)
    cout << map[r][c];
    cout << "\n";
//  }
}
                
//With every cell numbered (-1) except illudium phosdex (0) and lava (-2), use map[illudiumY][illudiumX] to +1 every cell around it to the edge.



  return 0;
}
/*
int BFS(int map[r][c]) {            //This is basically a findPath() but a bad attempt.
        Queue q;                    //create the queue
        q.enqueue(illudiumPath);    //source node
    for (map[r][c] == white) {      //if not visited
    q.enqueue(map[r][c]);           //add to the queue
    map[r][c] = grey;               //now mark as visisted
}
    while (q != isEmpty()) {        //while the queue is not empty
    q.dequeue(map[r][c])            //remove the vertex from the queue
    processNeighbors();             //get adjacent vertices from the parent node
}
    for (map[r][c] == white) {      //if vertex is not visited
    q.enqueue(map[r][c]);           //add to the queue
    map[r][c] == grey;              //mark as visited
}
        
return 0;
}


North = [c,r+1]
South = [c,r-1]
East  = [c+1,r]
West  = [c-1,r]

Odds:
Northeast = [c+1,r+1]
Northwest = [c-1,r+1]

Evens:
Southeast = [c+1,r-1]
Southwest = [c-1,r-1]

void processNeighbors(int map[r][c]) {

for (c%2 == 1) {    //The odd cases
  if 
  }

for (c%2 == 0) {    //The even cases
  if
  }

}
*/


And my queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#ifndef _QUEUE_H
#define _QUEUE_H

const int MAX_QUEUE_SIZE = 20;

enum QueueExceptions {
  E_QUEUE_EMPTY,
  E_QUEUE_FULL,
  E_ARRAY_OUT_OF_BOUNDS
};

class Queue {
 public:
  Queue(void) {
    head = 0;
    tail = 0;
    count = 0; 
  }
  ~Queue(void) { }

  void clear(void) { 
    head = 0;
    tail = 0;
    count = 0;
  }
  bool isEmpty(void) {
    return !count;
  }
  int size(void) {
    return count;
  }

void Queue::enqueue(int d) throw (int) {

  if (count == MAX_QUEUE_SIZE)
    throw E_QUEUE_FULL;

  data[tail] = d;
  tail = (tail + 1) % MAX_QUEUE_SIZE;
  count++;
}

int Queue::dequeue(void) throw(int) {
  int d;

  if (count == 0)
    throw E_QUEUE_EMPTY;

  d = data[head];
  head = (head + 1) % MAX_QUEUE_SIZE;
  count--;

  return d;
}

//  void enqueue(int) throw (int);
//  int dequeue(void) throw (int);
  int numberCells(int r, int c);

 private:
  int data[MAX_QUEUE_SIZE];
  int head,tail,count;
};

#endif 
Last edited on
Topic archived. No new replies allowed.