数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究C++ 程序用于查找在矩阵中两个单元格之间是否存在路径
在本文中，我们将讨论一个程序来查找给定矩阵中两个单元格之间是否存在路径。
假设我们给定一个方形矩阵，其可能值为 0、1、2 和 3。这里，
- 0 表示空白墙
- 1 表示源
- 2 表示目标
- 3 表示空白单元格
矩阵中只能有一个源和一个目标。该程序用来查看在给定矩阵中是否在沿四个可能方向（但不是对角线）移动的情况下从源到目标存在路径。
示例
#include<bits/stdc++.h>
using namespace std;
//creating a possible graph from given array
class use_graph {
int W;
list <int> *adj;
public :
use_graph( int W ){
this->W = W;
adj = new list<int>[W];
}
void add_side( int source , int dest );
bool search ( int source , int dest);
};
//function to add sides
void use_graph :: add_side ( int source , int dest ){
adj[source].push_back(dest);
adj[dest].push_back(source);
}
//function to perform BFS
bool use_graph :: search(int source, int dest) {
if (source == dest)
return true;
// initializing elements
bool *visited = new bool[W];
for (int i = 0; i < W; i++)
visited[i] = false;
list<int> queue;
//marking elements visited and removing them from queue
visited[source] = true;
queue.push_back(source);
//moving to the adjacent vertices
list<int>::iterator i;
while (!queue.empty()){
source = queue.front();
queue.pop_front();
for(i=adj[source].begin();i!=adj[source].end(); ++i) {
if (*i == dest)
return true;
if (!visited[*i]) {
visited[*i] = true;
queue.push_back(*i);
}
}
}
//if destination is not reached
return false;
}
bool is_okay(int i, int j, int M[][4]) {
if ((i < 0 || i >= 4) || (j < 0 || j >= 4 ) || M[i][j] == 0)
return false;
return true;
}
bool find(int M[][4]) {
int source , dest ;
int W = 4*4+2;
use_graph g(W);
int k = 1 ;
for (int i =0 ; i < 4 ; i++){
for (int j = 0 ; j < 4; j++){
if (M[i][j] != 0){
if ( is_okay ( i , j+1 , M ) )
g.add_side ( k , k+1 );
if ( is_okay ( i , j-1 , M ) )
g.add_side ( k , k-1 );
if (j < 4-1 && is_okay ( i+1 , j , M ) )
g.add_side ( k , k+4 );
if ( i > 0 && is_okay ( i-1 , j , M ) )
g.add_side ( k , k-4 );
}
if( M[i][j] == 1 )
source = k ;
if (M[i][j] == 2)
dest = k;
k++;
}
}
return g.search (source, dest) ;
}
int main(){
int M[4][4] = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 0 , 3 },{ 0 , 0 , 3 , 0 }};
(find(M) == true) ?
cout << "Possible" : cout << "Not Possible" <<endl ;
return 0;
}输出
Not Possible
更新于： 03-Oct-2019
137 次浏览
广告