C# Finding largest connected area of adjacent empty cells (string[,]) -
i'm trying find largest connected area of adjacent empty cells (diagonal connection counts).
for example if have matrix (" "-empty, "f"-filled)
{" "," "," ","f"}, {"f","f","f"," "}, {" "," ","f"," "} the result should be:
{"*","*","*","f"}, {"f","f","f","*"}, {" "," ","f","*"} any other ideas except old bfs/dfs?
here working code (solved 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]; (int row = 0; row < mrow; row++) { console.writeline(); console.writeline("row {0}:", row); console.writeline(); (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) { (int row = 0; row < mrow; row++) { (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 + "")); (int row = 0; row < mrow; row++) { (int col = 0; col < mcol; col++) { if (matrix[row, col].equals(" ") == true) { stack<tuple<int, int>> = 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) marked \'"+areacalculated.elementat(0).item1 + "\' symbol , contains " + areacalculated.elementat(0).item2 + " cells."); // console.writeline(areacalculated.elementat(areacalculated.count - 1).item1 + " " + areacalculated.elementat(areacalculated.count - 1).item2); } } }
thanks exercise, attempt
var wspace = new list<tuple<int, int>>(); string[,] cells = { { "f", " ", "f", "f", "f", "f", " " }, { "f", "f", "f", " ", "f", "f", " " }, { "f", " ", "f", " ", "f", " ", "f" }, { "f", "f", " ", "f", "f", " ", "f" }, { "f", " ", "f", " ", "f", " ", "f" } }; (int = 0; < cells.getlength(0); i++) (int j = 0; j < cells.getlength(1); j++) if (cells[i, j] == " ") wspace.add(new tuple<int, int>(i, j)); var region = new list<tuple<int, int>>(); var pre = new list<tuple<int, int>>(); var regions = new list<list<tuple<int, int>>>(); region.add(wspace.first()); wspace = wspace.skip(1).tolist(); for(int z=0; z<wspace.count(); z++) { var pos = wspace[z]; bool keep = true; (int = -1; < 2 && keep; i++) { (int j = -1; j < 2 && keep; j++) { if (region.any(x => x.item1 == (pos.item1 + i) && x.item2 == (pos.item2 + j))) { pre.reverse(); wspace.addrange(pre); pre.clear(); region.add(pos); keep = false; } } } if (keep && (pos.item1 > region.last().item1) && (pos.item2 > region.last().item2)) { regions.add(region.tolist()); region.clear(); region.add(pos); } else if (keep) pre.add(pos); } regions.add(region); region = regions.orderby(x => x.count).last().orderby(s => s.item1 * cells.getlength(1) + s.item2).tolist(); region.foreach(x => console.writeline("array: {0} key: {1}", x.item1 + 1, x.item2 + 1)); so far worked well, try , tell me
actual output
array: 2 key: 4 array: 3 key: 2 array: 3 key: 4 array: 4 key: 3 array: 5 key: 2 array: 5 key: 4
Comments
Post a Comment