인접한 빈 셀의 최대 연결 영역 (대각선 연결 개수)을 찾으려고합니다. 예를 들어 C# 인접한 빈 셀 (문자열 [,])의 가장 큰 연결 영역 찾기
이 같은 행렬이있는 경우
(""- 빈을, "F"채워진){" "," "," ","F"},
{"F","F","F"," "},
{" "," ","F"," "}
결과는해야한다 : 좋은 제외
{"*","*","*","F"},
{"F","F","F","*"},
{" "," ","F","*"}
다른 아이디어 이전 BFS/DFS? 여기
내 (BFS와 해결) 작업 코드 : 운동에 대한using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _09.LargestConnectedArea
{
class Program
{
public static string[,] matrix;
public static int mRow, mCol;
public static void Input(string mode = "mid")
{
if (mode.Equals("top"))
{
matrix = new string[4, 4]{
{" "," "," "," "},
{" "," "," "," "},
{"F"," "," ","F"},
{" ","F","F"," "}
};
mRow = matrix.GetLength(1);
mCol = matrix.GetLength(0);
}
else if (mode.Equals("mid"))
{
matrix = new string[4, 4]{
{"F","F","F"," "},
{" "," "," "," "},
{"F"," "," ","F"},
{"F","F","F","F"}
};
mRow = matrix.GetLength(1);
mCol = matrix.GetLength(0);
}
else if (mode == "test")
{
// matrix = new string[4, 4];
matrix = new string[7, 4]{
{" ","F","F"," "},
{"F","F"," "," "},
{" "," "," ","F"},
{"F","F"," "," "},
{" ","F"," ","F"},
{" ","F"," ","F"},
{" ","F"," ","F"}
};
mRow = 7;
mCol = 4;
}
else
{
Console.Write("maxrow: ");
mRow = int.Parse(Console.ReadLine());
Console.Write("maxcol: ");
mCol = int.Parse(Console.ReadLine());
matrix = new string[mRow, mCol];
for (int row = 0; row < mRow; row++)
{
Console.WriteLine();
Console.WriteLine("Row {0}:", row);
Console.WriteLine();
for (int col = 0; col < mCol; col++)
{
Console.Write("Element {0}:", col);
matrix[row, col] = Console.ReadLine();
}
}
}
}
public static int BFS(Stack<Tuple<int, int>> currPath, string symbol = "*", int counter = 0)
{
if (currPath.Count == 0)
{
return counter;
}
else
{
;
Tuple<int, int> top = new Tuple<int, int>(currPath.Peek().Item1, currPath.Pop().Item2);
matrix[top.Item1, top.Item2] = symbol;
counter++;
//top TEST: PASSED
#region
if (top.Item1 > 0)
{
//_X_
if (matrix[top.Item1 - 1, top.Item2].Equals(" "))
{
matrix[top.Item1 - 1, top.Item2] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 - 1, top.Item2));
}
//X__
if (top.Item2 > 0)
{
if (matrix[top.Item1 - 1, top.Item2 - 1].Equals(" "))
{
matrix[top.Item1 - 1, top.Item2 - 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 - 1, top.Item2 - 1));
}
}
//__X
if (top.Item2 < mCol - 1)
{
if (matrix[top.Item1 - 1, top.Item2 + 1].Equals(" "))
{
matrix[top.Item1 - 1, top.Item2 + 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 - 1, top.Item2 + 1));
}
}
}
#endregion
//mid TEST: PASSED
#region
if (top.Item2 > 0)
{
if (matrix[top.Item1, top.Item2 - 1].Equals(" "))
{
matrix[top.Item1, top.Item2 - 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1, top.Item2 - 1));
}
}
if (top.Item2 < mCol - 1)
{
if (matrix[top.Item1, top.Item2 + 1].Equals(" "))
{
matrix[top.Item1, top.Item2 + 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1, top.Item2 + 1));
}
}
#endregion
//bot TEST: PASSED
#region
if (top.Item1 < mRow - 1)
{
//_X_
if (matrix[top.Item1 + 1, top.Item2].Equals(" "))
{
matrix[top.Item1 + 1, top.Item2] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 + 1, top.Item2));
}
//X__
if (top.Item2 > 0)
{
if (matrix[top.Item1 + 1, top.Item2 - 1].Equals(" "))
{
matrix[top.Item1 + 1, top.Item2 - 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 + 1, top.Item2 - 1));
}
}
//__X
if (top.Item2 < mCol - 1)
{
if (matrix[top.Item1 + 1, top.Item2 + 1].Equals(" "))
{
matrix[top.Item1 + 1, top.Item2 + 1] = symbol;
currPath.Push(new Tuple<int, int>(top.Item1 + 1, top.Item2 + 1));
}
}
}
#endregion
return BFS(currPath, symbol, counter);
}
}
public static void Print(string[,] a)
{
for (int row = 0; row < mRow; row++)
{
for (int col = 0; col < mCol; col++)
{
Console.Write("\'{0}\' ", a[row, col]);
}
Console.WriteLine();
}
Console.WriteLine();
}
static void Main(string[] args)
{
Input("test");
Print(matrix);
List<Tuple<char, int>> areaCalculated = new List<Tuple<char, int>>();
char symbol = '1';
//Console.WriteLine(BFS(a, symbol + ""));
for (int row = 0; row < mRow; row++)
{
for (int col = 0; col < mCol; col++)
{
if (matrix[row, col].Equals(" ") == true)
{
Stack<Tuple<int, int>> a = new Stack<Tuple<int, int>>();
a.Push(new Tuple<int, int>(row, col));
areaCalculated.Add(new Tuple<char, int>(symbol, BFS(a, symbol + "")));
symbol++;
}
}
}
areaCalculated.Sort((x, y) => y.Item2.CompareTo(x.Item2));
Print(matrix);
Console.WriteLine("The largest connected area of adjacent empty cells(diagonal connection counts) is marked with the \'"+areaCalculated.ElementAt(0).Item1 + "\' symbol and contains " + areaCalculated.ElementAt(0).Item2 + " cells.");
// Console.WriteLine(areaCalculated.ElementAt(areaCalculated.Count - 1).Item1 + " " + areaCalculated.ElementAt(areaCalculated.Count - 1).Item2);
}
}
}
정의 인접한. 인접한 셀이 같은 행에만있는 것을 의미합니까, 아니면 열을 포함합니까? 결과는 인접한 행이 대각선을 포함하고 있다는 것을 의미합니다. 마지막 행의 마지막 행에'* '가 있기 때문에 –
코드를 게시하거나 시도가 어떻게 달라 졌는지에 대해 최소한 몇 줄의 설명을 게시하십시오. 솔루션이 작동한다면, 이것은 http://codereview.stackexchange.com/에 더 잘 맞는 것처럼 보입니다. –
옆에있는 말은 적어도 하나의 공통 에지/측면이있는 셀을 의미합니다. 그리고 여기에 게시하는 것에 대해 유감스럽게 생각합니다 (저는 stackoverflow를 처음 사용합니다). 어쩌면 당신 말이 맞을 것입니다, 아마도 그것은 codereview를위한 것입니다. 제가 여기에 올린 이유는 신선한 아이디어를 모으고 아마 제 것보다 더 나은 해결책을 찾는 것입니다. P. 나는 질문을 편집하고 코드를 게시 할 것이다. :) – BobsunShirov