معطى مصفوفة ثنائية مكونه من 0 و 1 . المطلوب ايجاد بئر.
بئر هو الوضع الذي فيه السطر K مكون فقط من اصفار وفي العامود K فقط الرقم 1, نقطة الالتقاء هي 0, مثال:
0 1 1 1 1 0
0 0 1 1 0 0
0 0 1 1 0 1
0 0 0 0 0 0
0 0 1 1 0 1
1 1 1 0 1 0
في هذه المصفوفه الاجابة هي K=3
يجب حل المسألة بنجاعة أقل من (O(n^2
لا يهم باي لغة الحل فانا استطيع الترجمة من كل اللغات الى C#
محاولتي الاولى لكنها ايضا (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;
}
قد تكون هناك طريقة O(n) لكن ساعدني على فهم المطلوب. أنا لم افهم شرحك كذلك لا افهم C# هل من الممكن ترجمة الخوارزمية الى pseudocode أو C++ أفضل.
لا داعي لقد وجدت الحل وهو ب 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, j] == 1) return -1;
for (i = 0; i < mat.GetLength(0); i++)
{
if (mat[i, j] == 0 && i != j)
return -1;
}
return j;
}
الفكرة هي التخلي عن جميع الاحتمالات اللتي من المستحيل ان يكون بها بئر ونبقى في النهاية مع احتمال واحد فقط ثم نفحصه
البساوودوكود
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 to do is to eliminate all options except one, and then test it.
Set i=0, j=1
Check cell (i,j)
If (i,j)=0, there's no hole j, set j=j+1.
If (i,j)=1, there's no hole i, set i=j, j=j+1.
Repeat until j=N, then test if hole i exists.
N-1 steps for the eliminations
2N-1 steps for the checking hole i
Total - O(N).
التعليقات