Converting memset and struct to newer notation

Question

I'm taking this C++ program and am trying to replace some of the older structures like memset (which I don't completely understand) and struct with newer language optimized for C++11. The program works as is and I am just trying to further my understanding by playing with the code.

"Hike on a Graph" is played on a board on which an undirected graph with colored edges. The graph is complete and has all loops; for any two locations there is exactly one edge (arrow) between them. The arrows are colored. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players move their pieces. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same color as the arrow between the two opponents' pieces.

In the sixties a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.

Input Specification:

The input file contains several test cases. Each test case starts with the number n. Input is terminated by n=0. Otherwise, 1<=n<=50. Then follow three integers p1, p2, p3 with 1<=pi<=n denoting the starting locations of the game pieces. The colors of the arrows are given next as a m×m matrix of whitespace-separated lower-case letters. The element mij denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical.

Output Specification:

For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word "impossible" if that is not possible for the given board and starting locations.

Example undirected graph for the first two inputs in the example below

Input:

3 1 2 3
r b r
b b b
r b r
2 1 2 2
y g
g y
1 1 1 1
a
2 1 1 1
a b
b d
2 1 2 2
a b
b a
2 1 2 2
a b
b b
2 1 2 2
b b
b b
2 1 2 2
b b
b a
3 1 2 3
a a a
a a a
a a a
3 1 2 3
a b a
b a b
a b a
3 1 2 3
a b a
b b b
a b a

Output:

2
impossible
0
0
impossible
1
1
2
2
impossible
2

---

#include <iostream>
#include <cstdio>
#include <cstring>
#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;
        }
    }
}

Answer 1

Comments on code

Note this code and this comment say different things

memset(visited,-1,sizeof(visited));
//int visited[51][51][51] = { -1 };

Every byte in the visited is being set to -1. There are multiple bytes in an int. If it works you are just getting lucky.

3.9.1 Fundamental types [basic.fundamental] Paragraph 7 of n3936

Types bool, char, char16_t, char32_t, wchar_t, and the signed and unsigned integer types are collectively called integral types. A synonym for integral type is integer type. The representations of integral types shall define values by use of a pure binary numeration system. [ Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types. —end example ]

Why split it up like this:

    //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();

Just copy the vertix

    vertix v = nodes.front();
    nodes.pop();

Arrays are zero indexed in C++

    //now look at all neighbors
    for(int i = 1; i <= n; i++)

SO this is either wrong or looks wierd.

Don't need two phase read:

            cin >> s;
            arr[i][j] = s;

Can just do:

            cin >> rr[i][j];

Algorithm

Basically your code is C.

You should be wrapping state into objects. Your graph is represented by a global

char arr[51][51];

Sure. But why not have a graph class. Then you can have more than one graph.

Also you search algorithm uses another glboal.

int visited[51][51][51];

Put this state into another object. Then you can use the Visitor Pattern to do your traversal.