In the following C++ code, replace memset (within the function bfs) with an alte

Question

In the following C++ code, replace memset (within the function bfs) with an alternative operation that will initialize the array "visited" in the same way.

#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

int visited[51][51][51];
char arr[51][51];

struct Vertex
{
int a;
   int b;
   int c;
   int t;
  
   //adding default vals to the struct
Vertex(int p1,int p2,int p3,int d)
   {
       a = p1;
       b = p2;
       c = p3;
       t = d;
   }
};

void bfs (int n, int p1, int p2, int p3)
{
   queue<Vertex> nodes;
   memset(visited,-1,sizeof(visited));
   //int visited[51][51][51] = { -1 };
   nodes.push(Vertex(p1,p2,p3,0));
   visited[p1][p2][p3] = 0;
   //queue traversal
   while(!nodes.empty())
   {
       //dequeue a vertex from queue
       int a = nodes.front().a;
       int b = nodes.front().b;
       int c = nodes.front().c;
       int t = nodes.front().t;
       nodes.pop();
       //now look at all neighbors
       for(int i = 1; i <= n; i++)
       {  
           //if we're looking at the node or the edge we're traveling on isn't the same as color connecting p2 and p3
           if(i == a || arr[a][i] != arr[b][c])
           {
               continue;
           }
           //if point has been looked at
           if(visited[i][b][c] != -1)
           {
               continue;
           }
           //if it hasn't been processed yet do that now
           nodes.push(Vertex(i,b,c,t+1));
           //cout << "p1:t+1=" << t+1 << endl;
           visited[i][b][c] = t+1;
       }
       for(int i = 1; i <= n; i++)
       {
           if(i == b || arr[b][i] != arr[a][c])
           {
               continue;
           }
if(visited[a][i][c] != -1)
           {
               continue;
           }
nodes.push(Vertex(a,i,c,t+1));
visited[a][i][c] = t+1;
}
for(int i = 1; i <= n; i++)
{
if(i == c || arr[c][i] != arr[a][b])
           {
               continue;
           }
if(visited[a][b][i] != -1)
           {
               continue;
           }
           nodes.push(Vertex(a,b,i,t+1));
           visited[a][b][i] = t+1;
       }
   }
}

int main ( )
{
   char s;
   int n,p1,p2,p3;
   while (cin >> n)   //read in number of nodes
   {
       if(n == 0)
       {
           break;
       }
       cin >> p1 >> p2 >> p3;
       //read in the array
       for ( int i = 1; i <= n ; i++ )
       {
           for ( int j = 1 ; j <= n ; j++ )
           {
               cin >> s;
               arr[i][j] = s;
               //cout << arr[i][j] << " ";
           }
           //cout << endl;
       }
      
       int soln;
       bool beginCondition = true;
       bfs(n,p1,p2,p3);
       //if the node isn't equal to infinity, set soln to visited node val and iterate.
       for(int i = 1; i <= n ; i++)
       {
           if(visited[i][i][i] != -1)
           {
               //cout << "Visited!" << visited[i][i][i] << endl;
               //cout << "Soln:" << soln << endl;
               if(beginCondition)
               {
                   soln = visited[i][i][i];
                   beginCondition = false;
               }
               else
               {
                   soln = min(soln,visited[i][i][i]);
               }
           }
       }

       if(beginCondition)
       {
           cout << "impossible" << endl;
       }
       else
       {
           cout << soln << endl;
       }
   }
}

-----------------------------------------------------------------------------------------------------------------

Example Input (each run is one line of integers and an array of a size that matches the first int val):

Example Output (solution is number or "impossible"):

Explanation / Answer

replace:

memset(visited,-1,sizeof(visited));

with:

for(int i=0;i<51;i++){
   for(int j=0;j<51;j++){
       for(int k=0;k<51;k++){
           visited[i][j][k]=-1;
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.