我正在寻找一些面试问题,但偶然发现了一个问题:
有一个mxn数组。数组中的一个块用1表示,0表示没有块。您应该在数组中找到对象的数量。一个对象不过是一组水平和/或垂直连接的块。
例如
0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0
答:此数组中有2个对象。L形对象和最后一行中的对象。
我在想出一种可以捕捉“ u”(如下图)形状的算法时遇到了麻烦。我应该如何处理?
0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0
这在C#中有效
static void Main() { int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } }; Console.WriteLine(GetNumber(array)); Console.ReadKey(); } static int GetNumber(int[][] array) { int objects = 0; for (int i = 0; i < array.Length; i++) for (int j = 0; j < array[i].Length; j++) if (ClearObjects(array, i, j)) objects++; return objects; } static bool ClearObjects(int[][] array, int x, int y) { if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false; if (array[x][y] == 1) { array[x][y] = 0; ClearObjects(array, x - 1, y); ClearObjects(array, x + 1, y); ClearObjects(array, x, y - 1); ClearObjects(array, x, y + 1); return true; } return false; }