J'ai un tableau 2-D qui contient 3 types d'éléments:
La règle est la suivante:
Le contaminant peut s'infiltrer à travers l'eau mais pas à travers les roches.
Disons que j'ai le tableau d'entrée suivant:
public static string[,] GenerateContaminant(int row, int column, string[,] arr)
{
string[,] result = new string[row, column];
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
result[i, j] = arr[i, j];
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
if (result[i, j] == "C")
{
for (int a = 0; a < row; a++)
{
if (result[i, a] == "W")
{
result[i, a] = "C";
}
}
for (int b = 0; b < column; b++)
{
if (result[b, j] == "W")
{
result[b, j] = "C";
}
}
}
}
}
return result;
}
Donc les cellules qui ont 'C' comme leur valeur dans le tableau ci-dessus peut contaminer dans la même ligne et la même colonne si de l'eau est présente.
Donc, la sortie aimerait quelque chose comme ceci:
CCCRW CRRRR RWWRW WWWRR WRRCC
Voici ma tentative naïve en C #:
WWWRW CRRRR RWWRW WWWRR WRRWC
Cela aussi me donne de mauvais résultats.
Voici le lien sur lequel je travaille.
Je sais que je dois résoudre ce problème en utilisant via le retour en arrière et la récursivité, mais je ne suis pas en mesure de proposer un algorithme apt pour le faire.
Toute aide sera extrêmement appréciée.
3 Réponses :
Ceci peut être facilement résolu en utilisant une adaptation de l ' Algorithme Lee .
L'adaptation est également appelée remplissage par inondation voir cette réponse pour un exemple de code .
Vous utiliseriez essentiellement une pile ou une file d'attente pour conserver les voisins valides d'une cellule contaminée. Ensuite, vous ajouteriez des voisins de voisins jusqu'à ce que vous atteigniez un arrêt (il n'y a plus de cellules W voisines d'une cellule C).
Existe-t-il une solution itérative possible?
@KunalMukherjee l'exemple de code fourni résout le problème en utilisant une approche itérative.
Je n'expliquerai pas ici l'algorithme de remplissage par inondation, car vous trouverez de nombreux tutoriels en ligne sur ce sujet.
Une autre façon de résoudre le problème est de s'infiltrer à plusieurs reprises dans une cellule jusqu'à ce qu'aucun mouvement ne se produise. Ce n'est pas très efficace mais simple à comprendre.
La solution devient plus lisible, si vous extrayez du code dans des méthodes d'assistance.
Cette méthode d'assistance récupère les voisins d'une cellule en prenant soin de ne pas dépasser les frontières. Il utilise un C # Iterator :
char[,] environment = {
{ 'W', 'W', 'W', 'R', 'W' },
{ 'C', 'R', 'R', 'R', 'R' },
{ 'R', 'W', 'W', 'R', 'W' },
{ 'W', 'W', 'W', 'R', 'R' },
{ 'W', 'R', 'R', 'W', 'C' }
};
var result = (char[,])environment.Clone(); // Creates a copy of the original.
bool didChange;
do {
Print(result);
didChange = false;
for (int i = 0; i < result.GetLength(0); i++) {
for (int j = 0; j < result.GetLength(1); j++) {
if (result[i, j] == 'W' &&
NeighborsOf(result, i, j).Any(n => n == 'C')) {
result[i, j] = 'C';
didChange = true;
}
}
}
} while (didChange);
Cette méthode imprime le tableau
private static void Print(char[,] env)
{
Console.Clear();
for (int i = 0; i < env.GetLength(0); i++) {
for (int j = 0; j < env.GetLength(1); j++) {
Console.Write(env[i, j]);
}
Console.WriteLine();
}
Thread.Sleep(1000);
}
La solution
private static IEnumerable<char> NeighborsOf(char[,] env, int i, int j)
{
if (i > 0) yield return env[i - 1, j];
if (i < env.GetLength(0) - 1) yield return env[i + 1, j];
if (j > 0) yield return env[i, j - 1];
if (j < env.GetLength(1) - 1) yield return env[i, j + 1];
}
Notez que je ne prenez un contaminant pour le répandre, mais commencez plutôt par de l'eau et regardez s'il y a un contaminant autour. Cela me permet de faire au plus une affectation par boucle.
Vous pouvez également créer une copie à chaque boucle (principale) pour obtenir une simulation réaliste dans le temps. Dans l'état actuel du code, un contaminant peut se répandre sur plusieurs cellules d'affilée dans une boucle.
Cela mute le tableau d'origine
Oui, mais comme je l'ai écrit, c'est à vous de créer une copie si vous souhaitez conserver l'original.
Donc le yield return donne tous les voisins d'une cellule? Pouvez-vous expliquer cette partie && NeighboursOf (arr, i, j) .Any (n => n == "C")) ?
vous avez fait bon usage du rendement de rendement et bien géré les conditions aux limites dans la méthode neighboursOf , très intelligent
yield return est une sorte de magie. Il renvoie un élément d'une énumération mais ne quitte pas la méthode. Ce qu'il fait, c'est renvoyer les 4 voisins, sinon à une frontière. Si vous préférez, vous pouvez également utiliser la solution classique consistant à renvoyer une List à la place. .Any (n => n == 'C') renvoie true si l'un de ces voisins est un contaminant. La condition est transmise sous la forme Lambda expression . Vous pouvez bien sûr également parcourir les voisins dans une boucle for.
Puisque les solutions ici semblent itératives, je vais en fournir une autre relativement simple en utilisant la récursivité.
En résumé, cet algorithme itère à travers tous les n éléments du tableau 2D et en trouvant un "C", commence un processus récursif de conversion de tous les éléments "W" adjacents en "C". S'il n'y a pas d'éléments "W" adjacents, il met fin à la récursivité et continue son itération à travers le tableau. Il remplit essentiellement récursivement chaque composant connecté qui devrait être contaminé dans le tableau.
Cet algorithme parcourt chaque élément, puis implémente efficacement une recherche Depth-First qui se termine lorsqu'aucun élément adjacent ne peut être contaminé. La terminaison du DFS est importante et empêche le traitement répété inutile des éléments. Cet algorithme est également efficace en mémoire puisqu'il modifie le tableau en place.
Input: WWWRW CRRRR RWWRW WWWRR WRRWC Output: CCCRW CRRRR RWWRW WWWRR WRRCC
Voici ma solution ajouté au code du testeur complet à partir de votre lien Rextester. Je copie le tableau d'entrée au début car mon algorithme modifie le tableau qui lui est passé.
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
// Set up input.
string[,] arr = new string[,]
{
{ "W", "W", "W", "R", "W" },
{ "C", "R", "R", "R", "R" },
{ "R", "W", "W", "R", "W" },
{ "W", "W", "W", "R", "R" },
{ "W", "R", "R", "W", "C" }
};
// Actual algorithm for solution.
// Make a copy for result since recursive solution will modify array in place.
string[,] result = arr.Clone() as string[,];
GenerateContaminant(result);
printGrid("Input:", arr);
printGrid("Output:", result);
}
public static void GenerateContaminant(string[,] arr)
{
// Iterate through every element of the array and when you find a "C",
// propagate the contamination recursively to its neighbors.
for (int row = 0; row < arr.GetLength(0); row++)
{
for (int col = 0; col < arr.GetLength(1); col++)
{
if (arr[row, col] == "C") {
ContaminateRecurse(row, col, arr);
}
}
}
return;
}
// Recurse from a "C" element and see if its neighbors should be contaminated.
public static void ContaminateRecurse(int row, int col, string[,] arr)
{
arr[row, col] = "C";
// Top Neighbor
if (isValid(row-1, col, arr)) {
ContaminateRecurse(row-1, col, arr);
}
// Bottom Neighbor
if (isValid(row+1, col, arr)) {
ContaminateRecurse(row+1, col, arr);
}
// Left Neighbor
if (isValid(row, col-1, arr)) {
ContaminateRecurse(row, col-1, arr);
}
// Right Neighbor
if (isValid(row, col+1, arr)) {
ContaminateRecurse(row, col+1, arr);
}
return;
}
// Makes sure that an element index is within the bounds of the array and is a 'W'.
public static bool isValid(int row, int col, string[,] arr) {
if ((0 <= row && row < arr.GetLength(0)) &&
(0 <= col && col < arr.GetLength(1)) &&
arr[row,col] == "W") {
return true;
}
else {
return false;
}
}
// Write grid to console.
public static void printGrid(string label, string[,] result) {
Console.Write(label);
Console.WriteLine();
for (int rowValue = 0; rowValue < result.GetLength(0); rowValue++) {
for (int colValue = 0; colValue < result.GetLength(1); colValue++) {
Console.Write(result[rowValue, colValue]);
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
public static void GenerateContaminant(string[,] arr)
{
// Iterate through every element of the array and when you find a "C",
// propagate the contamination recursively to its neighbors.
for (int row = 0; row < arr.GetLength(0); row++)
{
for (int col = 0; col < arr.GetLength(1); col++)
{
if (arr[row, col] == "C") {
ContaminateRecurse(row, col, arr);
}
}
}
return;
}
// Recurse from a "C" element and see if its neighbors should be contaminated.
public static void ContaminateRecurse(int row, int col, string[,] arr)
{
arr[row, col] = "C";
// Top Neighbor
if (isValid(row-1, col, arr)) {
ContaminateRecurse(row-1, col, arr);
}
// Bottom Neighbor
if (isValid(row+1, col, arr)) {
ContaminateRecurse(row+1, col, arr);
}
// Left Neighbor
if (isValid(row, col-1, arr)) {
ContaminateRecurse(row, col-1, arr);
}
// Right Neighbor
if (isValid(row, col+1, arr)) {
ContaminateRecurse(row, col+1, arr);
}
return;
}
// Makes sure that an element index is within the bounds of the array and is a 'W'.
public static bool isValid(int row, int col, string[,] arr) {
if ((0 <= row && row < arr.GetLength(0)) &&
(0 <= col && col < arr.GetLength(1)) &&
arr[row,col] == "W") {
return true;
}
else {
return false;
}
}
p >
Le retour arrière est utile si vous devez rechercher un chemin vers une cible, car vous pouvez alors revenir en arrière dans des impasses. Mais ici, le contaminant ne va toujours que dans un seul sens et empruntera toujours tous les chemins possibles. Jetez un œil à l ' algorithme de remplissage par inondation .
@ OlivierJacot-Descombes Bien sûr, je vais y jeter un coup d'oeil, pouvez-vous suggérer un moyen de rectifier ma mise en œuvre naïve