複数のステップまたはジャンプが許可されている迷路のラット?
迷路のネズミの問題は、バックトラックのよく知られた問題の1つです。ここでは、ほとんど変化のない問題を確認します。 1つのNxN迷路Mが与えられたと仮定します。出発点は左上隅のM[0、0]で、目的地は右下隅のM [N – 1、N-1]です。 1匹のラットを出発点に置きます。私たちの目標は、ラットが目的地に到達するための始点から終点までの経路を見つけることです。ここでネズミはジャンプすることができます(バリエーション)。今、いくつかの制約があります
- ラットは右または下に移動できます。
- セルに0が含まれる迷路は、セルがブロックされていることを示します。
- ゼロ以外のセルは有効なパスを示しています。
- セル内の数字は、ラットがそのセルから最大ジャンプできる回数を示しています。
アルゴリズム
ratInMaze
begin if destination is reached, then print the solution matrix else 1. Place the current cell inside the solution matrix as 1 2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not. 3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not 4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0. end if end
例
#include <iostream> #define N 4 using namespace std; void dispSolution(int sol[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << sol[i][j] << " "; cout << endl; } } bool isSafe(int maze[N][N], int x, int y) { //check whether x,y is valid or not // when (x, y) is outside of the maze, then return false if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0) return true; return false; } bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) { if (x == N - 1 && y == N - 1) { //if destination is found, return true sol[x][y] = 1; return true; } if (isSafe(maze, x, y)) { sol[x][y] = 1; //mark 1 into solution matrix for (int i = 1; i <= maze[x][y] && i < N; i++) { if (ratMazeSolve(maze, x + i, y, sol)) //move right return true; if (ratMazeSolve(maze, x, y + i, sol)) //move down return true; } sol[x][y] = 0; //if the solution is not valid, then make it 0 return false; } return false; } bool solveMaze(int maze[N][N]) { int sol[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (!ratMazeSolve(maze, 0, 0, sol)) { cout << "Solution doesn't exist"; return false; } dispSolution(sol); return true; } main() { int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 }, { 0, 1, 0, 1 }, { 0, 0, 0, 1 } }; solveMaze(maze); }
出力
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
-
迷路の中のラットのためのCプログラム-バックトラッキング-2?
迷路の中のネズミも、バックトラックを利用する一般的な問題の1つです。私 迷路は、一部のセルがブロックされている2Dマトリックスです。セルの1つはソースセルであり、そこから開始する必要があります。そしてもう1つは、私たちが到達しなければならない目的地です。ブロックされたセルに移動せずに、送信元から宛先までのパスを見つける必要があります。未解決の迷路の写真を以下に示します。 そしてこれがその解決策です。 このパズルを解くために、最初にソースセルから始めて、パスがブロックされていない方向に移動します。道をたどると目的地にたどり着くことができれば、パズルは解かれます。そうでなければ、
-
Excel で CSV ファイルを複数のシートに結合する (簡単な手順)
Excel ファイルを操作していると、複数の CSV ファイルが作成されることがあります。現在、これらの CSV ファイルを 1 つのワークブックにマージすることが頻繁に必要になります。この記事では、Excel で CSV ファイルを複数のシートにマージするすべての手順を紹介します。 ここからソース CSV ファイルと最終的な結合ワークブックを無料でダウンロードできます! CSV ソース ファイル: 最終マージ ファイル: CSV ファイルを複数の Excel シートにマージする手順 たとえば、6 年生、7 年生、および 8 年生のレポート カード用に、複数の生徒のさまざまな科目用