C++で地雷のあるパスで最短の安全なルートを見つける
この問題では、行列mat[][]が与えられます。これは、0とマークされた地雷のあるパスを定義します。私たちのタスクは、地雷のあるパスで最短の安全なルートを見つけることです。
安全な道をたどるときは、安全でないために地雷の隣接するセル（左、右、上、下）を歩くことを避ける必要があります。
パスを通過する際のすべての有効な移動は-
です。- Left : mat[i][j] => mat[i-1][j] - Right : mat[i][j] => mat[i+1][j] - Top : mat[i][j] => mat[i][j - 1] - Bottom : mat[i][j] => mat[i][j + 1]
問題を理解するために例を見てみましょう
入力
mat[][] = {
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} 出力
length of shortest safe path is 7
説明
{
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} ソリューションアプローチ
この問題の簡単な解決策は、バックトラッキングを使用することです。しかし、解決策への道を見つける前に、アランドミンに隣接するすべてのセルを安全でないセルとしてマークします。ここで、最初の列のセルを開始するために、その位置から安全な各セルに移動し、それが宛先（最後の列の任意のセル）につながるかどうかを確認します。次に、目的地につながる可能性のあるすべての安全な位置について、目的地に到達するための最短経路を見つけます。可能であれば、経路の長さを返します
それ以外の場合は-1を返し、パスが見つからないことを示します
ソリューションの動作を説明するプログラム
例
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
bool isSafe(int mat[R][C], int isvisited[R][C], int x, int y){
if (mat[x][y] == 0 || isvisited[x][y])
return false;
return true;
}
bool isValid(int x, int y){
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
void unSafeCellsInPath(int mat[R][C]){
for (int i = 0; i < R; i++){
for (int j = 0; j < C; j++){
if (mat[i][j] == 0){
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++){
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
}
void findShortestSafeRouteRec(int mat[R][C], int isvisited[R][C], int i, int j, int &min_dist, int dist){
if (j == C-1){
min_dist = min(dist, min_dist);
return;
}
if (dist > min_dist)
return;
isvisited[i][j] = 1;
for (int k = 0; k < 4; k++){
if (isValid(i + rowNum[k], j + colNum[k]) && isSafe(mat, isvisited, i + rowNum[k], j + colNum[k])){
findShortestSafeRouteRec(mat, isvisited, i + rowNum[k], j + colNum[k], min_dist, dist + 1);
}
}
isvisited[i][j] = 0;
}
int findShortestSafeRoute(int mat[R][C]){
int minSafeDist = INT_MAX;
int isvisited[R][C];
unSafeCellsInPath(mat);
for (int i = 0; i < R; i++) {
if (mat[i][0] == 1) {
memset(isvisited, 0, sizeof isvisited);
findShortestSafeRouteRec(mat, isvisited, i, 0, minSafeDist, 0);
if(minSafeDist == C - 1)
break;
}
}
if (minSafeDist != INT_MAX)
return minSafeDist;
else
return -1;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
} 出力
Shortest Safe route Length is 10
代替ソリューション
この問題の別の解決策は、幅優先探索を使用することです。キューを使用して、最初の列から最後の列までのパスを見つけ、最初の列から最後の列までのパスの最小距離を返します。
ソリューションの動作を説明するプログラム
例
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
struct Key{
int x,y;
Key(int i,int j){ x=i;y=j;};
};
bool isValid(int x, int y) {
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
int findShortestSafeRoute(int mat[R][C]){
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == 0) {
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
int visited[R][C];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++)
visited[i][j] = -1;
}
queue<Key> distQueue;
for(int i=0;i<R;i++){
if(mat[i][0] == 1){
distQueue.push(Key(i,0));
visited[i][0] = 0;
}
}
while(!distQueue.empty()){
Key k = distQueue.front();
distQueue.pop();
int d = visited[k.x][k.y];
int x = k.x;
int y = k.y;
for (int k = 0; k < 4; k++) {
int xp = x + rowNum[k];
int yp = y + colNum[k];
if(isValid(xp,yp) && visited[xp][yp] == -1 && mat[xp][yp] == 1){
visited[xp][yp] = d+1;
distQueue.push(Key(xp,yp));
}
}
}
int pathLen = INT_MAX;
for(int i=0;i<R;i++){
if(mat[i][C-1] == 1 && visited[i][C-1] != -1){
pathLen = min(pathLen,visited[i][C-1]);
}
}
if(pathLen == INT_MAX)
return -1;
else
return pathLen;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
} 出力
Shortest Safe route Length is 10
-
ルートとリーフパスのペアがあり、合計がC++のルートのデータと等しいかどうかを確認します
この問題では、二分木が与えられます。そして、合計がルートのデータに等しいリーフパスへのルートにペアがあるかどうかを見つける必要があります。 ペアの値の合計がルートノードの値と等しくなるように、ルートノードとリーフノードの間にノードのペアが存在するかどうかを確認する必要があります。 問題を理解するために例を見てみましょう。 入力： 出力： はい 説明： ルートノード値7 合計値がルートノード（2、5）、（1、6）に等しいペア。 ソリューションアプローチ： ツリーをトラバースし、ハッシュを使用してペアを見つける必要があります。 このために、hashTab
-
C++で指定された制約を持つマトリックス内の最長パスを検索します
次数nの正方行列が1つあるとします。それはすべて異なる要素を持っています。したがって、パスに沿ったすべてのセルが1の差で昇順になるように、最大長のパスを見つける必要があります。1つのセルから4つの方向に移動できます。左、右、上、下。したがって、行列が-のような場合 1 2 9 5 3 8 4 6 7 したがって、出力は4になります。最長パスは6→7→8→9です。 この問題を解決するために、私たちはこの考えに従います。すべてのセルから始まる最長パスを計算します。すべてのセルの最長パスを取得したら、すべての最長パスの最大値を返します。