شكرًا جزيلًا
1
الفكرة هي التخلي عن جميع الاحتمالات اللتي من المستحيل ان يكون بها بئر ونبقى في النهاية مع احتمال واحد فقط ثم نفحصه البساوودوكود Lets look at cell (i,j), for i<>j: If it's 0, then there's no hole j (all the cells in column j must be 1, other than j,j). If it's 1, then there's no hole i (all the cells in row i must be 0). Conclusion: There can be only one hole (if any). So all we have
لا داعي لقد وجدت الحل وهو ب O(N) static int Hole_2(int[,] mat) { int i = 0, j = 1; while (j < mat.GetLength(1)) { if (mat[i, j] == 0) j++;// There Is No Hole In This Coloumn else if (mat[i, j] == 1)// There Is No Hole In This Row { i = j; j++; } } for (j = 0; j < mat.GetLength(1); j++) { if (mat[i, j] == 1) return -1; } j = i; if (mat[j,
محاولتي الاولى لكنها ايضا (O(n^2 public static int FindTheHole(int[,] mat) { int i = 0; int j = 0; while (i < mat.GetLength(0) && j < mat.GetLength(1)) { if (i == j) if (mat[i,j] == 0) j++; else { i++; j = 0; } else if (mat[j, i] == 1 && mat[i, j] == 0) j++; else { j = 0; i++; } } if (i < mat.Length) return i; else return -1; }