1568. حداقل تعداد روز برای قطع اتصال جزیره

1568. حداقل تعداد روز برای قطع اتصال جزیره
سختی: سخت
موضوعات: Array
، Depth-First Search
، Breadth-First Search
، Matrix
، Strongly Connected Component
به شما یک m x n
شبکه دودویی grid
کجا 1
نشان دهنده زمین و 0
نشان دهنده آب است یک جزیره حداکثر است 4- جهت (افقی یا عمودی) گروه متصل از 1
's
شبکه گفته می شود متصل است اگر داریم دقیقا یک جزیره، در غیر این صورت گفته می شود قطع شده است.
در یک روز، ما مجاز به تغییر یک تک سلول زمین هستیم (1)
به سلول آب (0)
.
بازگشت حداقل تعداد روز برای قطع شبکه.
مثال 1:
- ورودی: شبکه = [[0,1,1,0]،[0,1,1,0]،[0,0,0,0]]
- خروجی: 2
-
توضیح: حداقل 2 روز زمان نیاز داریم تا یک شبکه قطع شده را دریافت کنیم.\ تغییر زمین
grid[1][1]
وgrid[0][2]
به آب و 2 جزیره قطع شده.
مثال 2:
- ورودی: شبکه = [[1,1]]
- خروجی: 2
-
توضیح: شبکه آب کامل نیز قطع شده است
([[1,1]] -> [[0,0]])
،0
جزایر
محدودیت ها:
m == grid.length
n == grid[i].length
1
-
grid[i][j]
یا است0
یا1
.
اشاره:
- اگر شبکه قبلاً قطع شده است، 0 را برگردانید.
- در صورت تغییر یک زمین به آب، جزیره را قطع کنید، شماره 1 را برگردانید.
- در غیر این صورت 2 را برگردانید.
- حداکثر ظرف 2 روز می توانیم شبکه را قطع کنیم.
راه حل:
باید مراحل زیر را در نظر بگیریم:
مراحل حل مشکل:
-
اتصال اولیه را بررسی کنید: ابتدا، با تعیین اینکه آیا بیش از یک جزیره در شبکه وجود دارد، بررسی کنید که آیا شبکه قبلاً قطع شده است. اگر قبلاً قطع شده است، برگردید
0
. -
بررسی کنید که آیا حذف تکی جزیره را قطع می کند: در هر سلول شبکه تکرار کنید. تبدیل موقت سلول از
1
به0
(اگر باشد1
) و بررسی کنید که آیا شبکه با شمارش تعداد جزایر قطع می شود یا خیر. اگر تبدیل یک سلول تنها جزیره را قطع کرد، برگردید1
. -
قطع دو روزه: اگر هیچ تبدیل تک سلولی جزیره را قطع نکند، می توان با تبدیل هر دو سلول زمینی مجاور، شبکه را قطع کرد. بنابراین، بازگشت
2
.
توابع کلیدی:
- DFS (جستجوی عمقی اول) برای یافتن و شمارش جزایر
- متصل است برای بررسی اینکه آیا شبکه متصل است یا خیر.
بیایید این راه حل را در PHP پیاده سازی کنیم: 1568. حداقل تعداد روز برای قطع اتصال جزیره
// Example usage:
$grid1 = [
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]
];
echo minDays($grid1); // Output: 2
$grid2 = [
[1, 1]
];
echo minDays($grid2); // Output: 2
?>
توضیح:
-
minDays()
تابع منطق اصلی را مدیریت می کند. -
countIslands()
با استفاده از DFS چند جزیره را می شمارد. -
dfs()
تابع بازگشتی برای کشف شبکه و علامت گذاری سلول های زمین بازدید شده است.
لینک های تماس
اگر این مجموعه را مفید یافتید، لطفاً آن را در نظر بگیرید مخزن یک ستاره در GitHub یا اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود . حمایت شما برای من اهمیت زیادی دارد!
اگر محتوای مفیدتری مانند این میخواهید، در صورت تمایل من را دنبال کنید: