0
私は、次の割り当てに取り組んでいます：AからBへの幅優先探索のためのBFS Cで行列の（幅優先探索）++
書き込みソフトウェア、C、D、Eは、FANDはあなたのアルゴリズムの特性を比較します。
文字は、class Matrixによって作られたマトリックスに置かれます。 形成されたマトリックスのすべての要素は、bool visitedの位置、int r, int k（対応する行、列）、およびchar valueの位置を格納できるように、class Nodeのオブジェクトです。
マトリックス内の文字を見つけてその位置を返すこともできますが、幅広い最初の検索で文字から文字への検索方法はわかりません。私の最後の試行はBFS.cppですが、キューの使用がおそらく私の代わりにこれを行うことがわかりました。
文字の行列でchar Aからchar Bに移動するにはどうすればよいですか？以下
コードである：（莫大な量のために残念）
main.cppに
#include <iostream>
#include "Matrix.h"
#include "BFS.h"
using namespace std;
int main()
{
cout << "Hello world!" << endl;
{
//make matrix
Matrix matrix1 ;
cout<<"matrix1"<<endl<<matrix1<<endl;
matrix1.findNode('A');
matrix1.findNode('B');
BFS bfs1('A',matrix1,0) ;
}
cout << "Bye world!" << endl;
return 0;
}
Matrix.h
#ifndef MATRIX_H
#define MATRIX_H
#include "Node.h"
#include <iostream>
using namespace std ;
class Matrix
{
int size = 6 ;
Node** matrix ;
public:
Matrix();
virtual ~Matrix();
friend ostream& operator<<(ostream& out, Matrix &p) ;
Node& findNode(char _A) ;
protected:
private:
};
#endif // MATRIX_H
Matrix.cpp
#include "Matrix.h"
Matrix::Matrix()
{
//ctor
matrix = new Node*[size];
for(int r=0; r<size; r++){
matrix[r] = new Node[size];
}
// correct positions of nodes
for(int r=0; r<size; r++)
{
for(int k = 0; k<size;k++)
{
matrix[r][k].setPos(r,k) ;
}
}
// Now set characters A t/m F in fixed position
matrix[2][2].setValue('A') ;
matrix[0][0].setValue('B') ;
matrix[0][2].setValue('C') ;
matrix[4][1].setValue('D') ;
matrix[5][5].setValue('E') ;
matrix[5][0].setValue('F') ;
}
Matrix::~Matrix()
{
//dtor
for(int r=0; r<size; r++){
delete [] matrix[r];
}
delete [] matrix ;
}
ostream& operator<<(ostream& out, Matrix &p)
{
for(size_t r=0; r<p.size; r++)
{
for(size_t k = 0; k<p.size;k++)
{
out<<p.matrix[r][k].getValue()<<" " ;
}
out<<endl ;
}
out<<"____________________________"<<endl;
}
Node& Matrix::findNode(char _A)
{
bool found = false ;
Node ans ;
for(int r=0; r<size; r++)
{
for(int k = 0; k<size;k++)
{
if(matrix[r][k].getValue() == _A)
{
ans = matrix[r][k] ;
found = true ;
break ;
}
}
}
cout<<"Search for "<<_A<<" results:";
if (found)
{
cout<<" found: "<<ans<<endl ;
return ans ;
}
else
{
cout<<" not found."<<endl ;
}
}
Node.h
#ifndef NODE_H
#define NODE_H
#include <iostream>
using namespace std;
class Node // ctor, dtor, operator=, operator<<, setPos, setState, setValue
{
int r ; int k ; //row nr and column nr, because used in BFS
bool visited ;
char value ;
public:
Node(int _r = 0, int _k = 0,char _value = '_', bool _visited = false);
virtual ~Node();
Node& operator=(const Node &p);
friend ostream& operator<<(ostream& out, Node &p);
void setPos(int _r, int _k);
void setState(bool _visited);
void setValue(char _value);
char getValue();
protected:
private:
};
#endif // NODE_H
Node.cpp
#include "Node.h"
// all this code is integrated in Node.h
Node::Node(int _r, int _k,char _value, bool _visited)
{
//ctor
// defaults specified in Node.h : 0 0 _ false
r = _r ; k = _k ; value = _value ; visited = _visited ;
}
Node::~Node()
{
//dtor
}
Node& Node::operator=(const Node &p)
{
r = p.r ; k = p.k ; value = p.value ; visited = p.visited ;
};
ostream& operator<<(ostream& out, Node &p)
{
out<<"["<<p.r<<"]["<<p.k<<"] has value '"<<p.value<<"'" ;
};
void Node::setPos(int _r, int _k)
{
r = _r ; k = _k ;
};
void Node::setState(bool _visited)
{
visited = _visited ;
};
void Node::setValue(char _value)
{
value = _value ;
};
char Node::getValue()
{
return value ;
};
BFS.h
#ifndef BFS_H
#define BFS_H
#include <vector>
#include "Matrix.h"
#include "Node.h"
//BFS algorithm:
/*
Step 1: Push the root node in the Stack.
Step 2: Loop until stack is empty.
Step 3: Peek the node of the stack.
Step 4: If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push it on stack.
Step 5: If the node does not have any unvisited child nodes, pop the node from the stack.
*/
// object of class BFS should be the queue of nodes to be checked
//class Node ; class Matrix ;
class BFS
{
//queue<Node> queueNodes;
vector<Node> fronts ;
public:
BFS(char _start, Matrix _matrix, int _distance);
virtual ~BFS();
friend bool& isPresent(vector<Node> _vector , Node& _n) ;
protected:
private:
};
#endif // BFS_H
BFS.cpp
#include "BFS.h"
BFS::BFS(char _start, Matrix _matrix, int _distance)
{
//ctor; form que
//determine startpoint
vector<Node> newfronts ;
fronts.push_back(_matrix.findNode(_start)) ;
cout<<"BFS made"<<endl;
for(int i = 0 ; i < _distance ; i++)
{
// determine the new fronts
for(size_t f = 0 ; f < sizeof(fronts) ; f++)
{
// do only if new item is not in newfronts OR fronts yet AND if does not exceed matrix dimensions
if (fronts[f].r - 1 !< 0)
{
Node up = _matrix[fronts[f].r - 1][fronts[f].k] ;
if (! isPresent(fronts, up) && ! isPresent(newfronts, up))
{
newfronts.push_back(up) ;
}
}
if (fronts[f].r + 1 !> _matrix.size)
{
Node down = _matrix[fronts[f].r + 1][fronts[f].k] ;
newfronts.push_back(down) ;
}
if (fronts[f].k + 1 !> _matrix.size)
{
Node right = _matrix[fronts[f].r][fronts[f].k + 1] ;
newfronts.push_back(right) ;
}
if (fronts[f].k - 1 !< 0)
{
Node left = _matrix[fronts[f].r][fronts[f].k - 1] ;
newfronts.push_back(left) ;
}
}
}
}
BFS::~BFS()
{
//dtor
}
bool isPresent(vector<Node> _vector , Node& _n)
{
bool present = false ;
for(size_t i = 0 ; i < sizeof(_vector) ; i++)
{
if(_vector[i] == _n)
present = true ;
}
return present ;
}
あなたはすでに、あなたの時間に感謝をここにするためにすべての方法を管理している場合。 :-)