נתאר את בעיית מציאת "בור" במערך דו-ממדי ריבועי:

קלט: מערך דו-ממדי ריבועי בגודל nn המלא באפסים ואחדים בלבד.

נגדיר ש- k הוא בור ( sink ) אם בשורה ה- k - ית כל הערכים הם 0, ובעמודה ה- k - ית כל

הערכים הם 1 (חוץ מהאיבר [ k][k ] עצמו שהוא 0).

פלט: האם קיים מספר k המהווה בור במערך? אם כן, יש להחזיר את ערכו אחרת יש להחזיר 1 -.

.

לדוגמא: במערך 3 A הוא "בור":

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

במערך B אין בור:

0 1 0 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

לצערי לא עולה בדעתי משהו שהוא טוב יותר מ-O(N²)

תחשוב כמה בורות יש לכל היותר ולמה ?

תמצא דרך לפסול שורה או עמודה , בדרך הכי קצרה שיש .

מישהו כבר נתקל בדיוק באותו התרגיל לפני כחודשיים:

http://hwzone.co.il/community/threads/534413-%D7%9E%D7%A0%D7%A1%D7%94-%D7%9C%D7%9E%D7%A6%D7%95%D7%90-%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D-%D7%99%D7%A2%D7%99%D7%9C-%D7%9C%D7%91%D7%A2%D7%99%D7%94-%D7%94%D7%91%D7%90%D7%94?highlight=%D7%91%D7%95%D7%A8#.UrbEMPQW38o

הסתכלתי בפוסט הזה ולא הבנתי.

לכל היותר יכול להיות בור אחד, לפסול שורה או עמודה בדרך הכי קצרה אומר בדיקה של כל אחד מהאיברים לא ?

אני מניח שזו עבודה להגשה ?

אתה פשוט רוצה את הפתרון ?

תיאורטית כן, אבל מעשית זה נותן לך יותר מידע. נניח שאתה מסתכל על איבר אחד במערך (לדוגמה, במיקום 5,7). מה זה אומר לך?

אני ממש לא רוצה את הפיתרון אלא עזרה עם אלוגריתם בכדי שאכתוב אותו בעצמי

ולכן אנחנו מנסים להכווין אותך לכיוון הנכון. תחשוב על השאלה שכתבתי.

תיאורטית כן, אבל מעשית זה נותן לך יותר מידע. נניח שאתה מסתכל על איבר אחד במערך (לדוגמה, במיקום 5,7). מה זה אומר לך?

מה נותן לי איבר מסויים ? לא הרבה נראה לי, בסה"כ מספר

התכוונתי איזה מידע שקשור לשאלה. אתה מסתכל על האיבר - יש בו 0 או 1. מה זה אומר לך?

אם יהיה בו 1 אני ארצה לרדת למטה לאותו index לחפש עוד 1

תחשוב יותר טוב. מה אתה יכול להסיק מיד​ אם האיבר הזה הוא 1?

תחשוב .

אני מניח שהפתרון לא יבוא לך תוך חמש דקות , במיוחד שאתה נתקל פעם ראשונה ביעילות .

קח בחשבון שהשאלה הזו ברמת קושי בינונית לאותה מטלה .

אם הוא 1 אין פה בור באותו השורה

יפה. ואם הוא 0?