در این مطلب، ویدئو دیوارها و دروازه ها – چند منبع BFS – Leetcode 286 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:11:47
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,160 –> 00:00:01,920
همه به بازگشت خوش آمدید و بیایید
2
00:00:01,920 –> 00:00:03,760
امروز یک کد دقیق تر بنویسیم، بنابراین امروز بیایید
3
00:00:03,760 –> 00:00:05,440
یک مشکل گراف دیگر را حل کنیم،
4
00:00:05,440 –> 00:00:08,480
دیوارها و دروازه ها، بنابراین یک شبکه m در n به ما داده می شود
5
00:00:08,480 –> 00:00:11,599
که در آن هر موقعیت
6
00:00:11,599 –> 00:00:14,240
می تواند سه مقدار ممکن داشته باشد، یک مقدار
7
00:00:14,240 –> 00:00:16,160
منفی که نشان دهنده
8
00:00:16,160 –> 00:00:18,720
دیواری است که یک مانع است که نشان دهنده یک دیوار است. ما
9
00:00:18,720 –> 00:00:19,760
مجاز به
10
00:00:19,760 –> 00:00:21,359
بازدید نیستیم ما مجاز به بازدید از این
11
00:00:21,359 –> 00:00:22,800
دیوارها نیستیم یک
12
00:00:22,800 –> 00:00:25,840
صفر که یک دروازه را مشخص می کند، بنابراین
13
00:00:25,840 –> 00:00:28,080
این نمونه ای از یک دروازه در این
14
00:00:28,080 –> 00:00:29,679
مورد است و مقدار سوم
15
00:00:29,679 –> 00:00:32,238
بی نهایت است که اساساً
16
00:00:32,238 –> 00:00:33,600
یک اتاق خالی را نشان می دهد
17
00:00:33,600 –> 00:00:36,160
و اساساً برای هر یک از آنها.
18
00:00:36,160 –> 00:00:38,480
اتاق خالی یا هر موقعیتی که به عنوان بی نهایت علامت گذاری شده است
19
00:00:38,480 –> 00:00:41,120
ابتدا می خواهیم تشخیص
20
00:00:41,120 –> 00:00:44,399
دهیم که نزدیک ترین دروازه به آن اتاق چیست و
21
00:00:44,399 –> 00:00:46,399
سپس می
22
00:00:46,399 –> 00:00:48,640
خواهیم فاصله آن اتاق تا نزدیک ترین دروازه را برداریم
23
00:00:48,640 –> 00:00:50,079
و سپس
24
00:00:50,079 –> 00:00:53,280
آن مقدار نامحدود را با آن جایگزین کنیم و
25
00:00:53,280 –> 00:00:55,680
اگر چنین است. اساساً غیرممکن است اگر یک
26
00:00:55,680 –> 00:00:58,079
موقعیت خالی نتواند به یک دروازه
27
00:00:58,079 –> 00:01:00,000
در نمودار ما برسد، اساساً ما
28
00:01:00,000 –> 00:01:01,440
آن موقعیت را به عنوان بینهایت ترک میکنیم،
29
00:01:01,440 –> 00:01:03,359
بنابراین به عنوان مثال اجازه دهید
30
00:01:03,359 –> 00:01:04,720
به این مثال
31
00:01:04,720 –> 00:01:07,119
نگاهی بیندازیم.
32
00:01:07,119 –> 00:01:08,240
این
33
00:01:08,240 –> 00:01:10,799
اتاق خالی از یک چاه دروازه چقدر دور است و می تواند در
34
00:01:10,799 –> 00:01:12,400
دو جهت برود و می تواند پایین بیاید
35
00:01:12,400 –> 00:01:13,920
که یک مانع است بنابراین ما
36
00:01:13,920 –> 00:01:15,439
اجازه نداریم به آن سمتی سفر
37
00:01:15,439 –> 00:01:17,360
کنیم که نمی توانیم بالا برویم یا به سمت درست آنها
38
00:01:17,360 –> 00:01:19,439
خارج از محدوده هستند، اما ما میتوانیم به سمت چپ برویم
39
00:01:19,439 –> 00:01:21,840
و البته درست در
40
00:01:21,840 –> 00:01:23,439
کنار آن یک دروازه است، بنابراین چیزی که در
41
00:01:23,439 –> 00:01:23,759
اینجا قرار میدهیم
42
00:01:23,759 –> 00:01:26,000
یک است به این معنی که این یک موقعیت
43
00:01:26,000 –> 00:01:27,280
با دروازه فاصله دارد
44
00:01:27,280 –> 00:01:29,280
و به طور مشابه این یکی چگونه است. دور است
45
00:01:29,280 –> 00:01:30,799
این از یک دروازه، یک
46
00:01:30,799 –> 00:01:33,680
دو سه موقعیت درست از یک دروازه، بنابراین
47
00:01:33,680 –> 00:01:35,119
ما میتوانیم یک سه را در اینجا قرار دهیم، میتوانیم یک
48
00:01:35,119 –> 00:01:36,720
دو را در اینجا قرار دهیم و یکی را اینجا،
49
00:01:36,720 –> 00:01:40,159
اوه، در مورد این یکی، ما میتوانیم یک
50
00:01:40,159 –> 00:01:43,600
دو سه بریم، بنابراین سه موقعیت
51
00:01:43,600 –> 00:01:45,600
از این است. دروازه اما اتفاقاً
52
00:01:45,600 –> 00:01:46,960
اگر به سمت راست برویم یک دروازه نزدیکتر وجود دارد
53
00:01:46,960 –> 00:01:48,960
و سپس به سمت راست بالا می رویم
54
00:01:48,960 –> 00:01:50,960
بنابراین دروازه نزدیکتر در واقع دو
55
00:01:50,960 –> 00:01:52,640
مکان دورتر است بنابراین ما دو نفر را
56
00:01:52,640 –> 00:01:55,040
در این موقعیت قرار می دهیم و حالا اگر
57
00:01:55,040 –> 00:01:56,719
یک دروازه وجود داشته باشد چه اتفاقی می افتد دروازه در اینجا چه چیزی را
58
00:01:56,719 –> 00:01:58,719
علامت گذاری می کنیم این دو و همچنین اساساً آنها
59
00:01:58,719 –> 00:01:59,600
به عنوان بی نهایت شروع می شوند
60
00:01:59,600 –> 00:02:01,200
و ما w باید این دو
61
00:02:01,200 –> 00:02:02,799
موقعیت را به عنوان بی نهایت رها کنید،
62
00:02:02,799 –> 00:02:05,280
بنابراین هر موقعیتی که نمی تواند از یک
63
00:02:05,280 –> 00:02:06,640
دروازه بازدید کند، به
64
00:02:06,640 –> 00:02:10,000
عنوان بی نهایت باقی می ماند، بنابراین اولین ایده
65
00:02:10,000 –> 00:02:11,840
ای که ممکن است برای این مشکل داشته باشید،
66
00:02:11,840 –> 00:02:13,520
اساسا برای هر موقعیتی است که می خواهیم
67
00:02:13,520 –> 00:02:15,200
بدانیم نزدیک ترین دروازه چیست چرا نمی توانیم
68
00:02:15,200 –> 00:02:17,040
ما فقط یک dfs را به سمت راست اجرا می
69
00:02:17,040 –> 00:02:20,080
کنیم تا زمانی که به دروازه
70
00:02:20,080 –> 00:02:22,080
برسیم یا می دانید
71
00:02:22,080 –> 00:02:23,680
که وقتی
72
00:02:23,680 –> 00:02:24,800
نزدیکترین دروازه را
73
00:02:24,800 –> 00:02:28,000
به آن موقعیت درست برمی گردانیم به هر موقعیتی که می توانیم می رسیم و سپس این کار را
74
00:02:28,000 –> 00:02:29,760
برای هر موقعیت در کل
75
00:02:29,760 –> 00:02:31,120
شبکه اکنون انجام می دهیم. پیچیدگی زمانی
76
00:02:31,120 –> 00:02:31,680
77
00:02:31,680 –> 00:02:34,160
آن چاه چقدر خواهد بود که یک dfs اساساً
78
00:02:34,160 –> 00:02:35,840
به اندازه شبکه خواهد بود و ما این
79
00:02:35,840 –> 00:02:37,120
کار را برای هر موقعیت
80
00:02:37,120 –> 00:02:38,319
در شبکه انجام خواهیم داد بنابراین اساساً
81
00:02:38,319 –> 00:02:39,440
چیزی شبیه m در
82
00:02:39,440 –> 00:02:42,640
n مربع خواهد بود. سوال این است که آیا میتوانیم
83
00:02:42,640 –> 00:02:44,239
بهتر از این پیچیدگی زمانی بزرگ عمل
84
00:02:44,239 –> 00:02:45,920
کنیم، بیایید یک راهحل bfs را
85
00:02:45,920 –> 00:02:47,840
درست امتحان کنیم، dfs را امتحان کنیم، بیایید
86
00:02:47,840 –> 00:02:49,519
ابتدا جستجوی گسترده را امتحان کنیم و
87
00:02:49,519 –> 00:02:51,280
ببینیم چه چیزی به ما منجر میشود.
88
00:02:51,280 –> 00:02:52,560
89
00:02:52,560 –> 00:02:54,560
در مورد این
90
00:02:54,560 –> 00:02:56,160
یکی ممکن است که بتوانیم
91
00:02:56,160 –> 00:02:57,760
کارهای مکرر را حذف کنیم، اگر به
92
00:02:57,760 –> 00:02:59,840
خوبی انجام دهیم، از اینجا شروع می کنیم و سپس
93
00:02:59,840 –> 00:03:01,599
از هر چهار جهت بازدید می کنیم
94
00:03:01,599 –> 00:03:04,239
و می بینیم که نزدیک ترین دروازه ای
95
00:03:04,239 –> 00:03:05,840
که می توانیم به
96
00:03:05,840 –> 00:03:07,519
آن برسیم کدام است، بنابراین از اینجا شروع می کنیم فاصله
97
00:03:07,519 –> 00:03:09,360
صفر فاصله ما یک طول می کشد تا
98
00:03:09,360 –> 00:03:10,800
به این موقعیت ها برسیم و در نهایت
99
00:03:10,800 –> 00:03:12,319
می توانیم فاصله دو را
100
00:03:12,319 –> 00:03:14,000
به دست آوریم تا این موقعیت را درست به دست آوریم، اما از آنجایی که
101
00:03:14,000 –> 00:03:15,760
نمی خواهیم یک گره را
102
00:03:15,760 –> 00:03:17,599
دو بار در همان موقعیت دو بار دوباره بازدید
103
00:03:17,599 –> 00:03:19,440
کنیم. میدانی دقیقاً این کار را انجام میدهی که
104
00:03:19,440 –> 00:03:21,040
وقتی به موقعیتی رسیدیم،
105
00:03:21,040 –> 00:03:22,560
آن را بهعنوان بازدید شده رها میکنیم، بنابراین
106
00:03:22,560 –> 00:03:24,720
میدانی اگر از اینجا به اینجا برویم،
107
00:03:24,720 –> 00:03:26,400
دو موقعیت برای ما میگیرد، بنابراین
108
00:03:26,400 –> 00:03:27,760
میتوانیم بگوییم خوب است برای این
109
00:03:27,760 –> 00:03:29,440
موقعیت، ما دو نفر طول کشید. اما وقتی
110
00:03:29,440 –> 00:03:31,440
به سمت راست بالا میرویم، به این موقعیت میرسیم،
111
00:03:31,440 –> 00:03:33,120
میدانید که واقعاً نمیتوانیم به سمت دیگری برویم،
112
00:03:33,120 –> 00:03:34,720
بنابراین اساساً این به
113
00:03:34,720 –> 00:03:36,159
عنوان یک بنبست باقی میماند،
114
00:03:36,159 –> 00:03:39,120
ما هرگز
115
00:03:39,120 –> 00:03:40,640
در این موقعیت درست فاصله نخواهیم گرفت، زیرا ما
116
00:03:40,640 –> 00:03:42,480
نمیخواهیم یک موقعیت را
117
00:03:42,480 –> 00:03:44,560
دوبار تکرار کنیم، نمیتوانیم به آن ادامه دهیم ck در جهتی
118
00:03:44,560 –> 00:03:45,680
که از
119
00:03:45,680 –> 00:03:49,280
آن آمدهایم، بنابراین راهحل bfs که از
120
00:03:49,280 –> 00:03:52,080
اتاقها شروع میشود، کار نمیکند، اگر
121
00:03:52,080 –> 00:03:53,280
بخواهیم یک
122
00:03:53,280 –> 00:03:56,000
o واقعی از m در n راهحل به دست
123
00:03:56,000 –> 00:03:57,840
آوریم، اگر آن را از اتاقها انجام دهیم، کار نمیکند، اما
124
00:03:57,840 –> 00:04:00,080
اجازه دهید راهحل خود را معکوس کنیم. کمی فکر کنید چرا
125
00:04:00,080 –> 00:04:02,560
یک راه حل bfs
126
00:04:02,560 –> 00:04:05,760
از دروازه ها انجام ندهیم، به عنوان مثال از این
127
00:04:05,760 –> 00:04:08,640
دروازه می توانیم بگوییم خوب، بیایید همه
128
00:04:08,640 –> 00:04:11,519
اتاق های مجاور را اساساً به این صورت علامت گذاری کنیم که بگوییم خوب است
129
00:04:11,519 –> 00:04:13,599
همه اتاق های مجاور یک
130
00:04:13,599 –> 00:04:15,040
فاصله
131
00:04:15,040 –> 00:04:17,600
از این دروازه دارند و سپس ادامه می دهیم.
132
00:04:17,600 –> 00:04:18,639
بنابراین از
133
00:04:18,639 –> 00:04:20,160
شما می دانید که این اتاق هیچ
134
00:04:20,160 –> 00:04:22,240
اتاق دیگری در مجاورت خود ندارد، اما این اتاق
135
00:04:22,240 –> 00:04:22,639
دارد،
136
00:04:22,639 –> 00:04:24,479
بنابراین می توانیم بگوییم خوب است برای این اتاق،
137
00:04:24,479 –> 00:04:26,160
در این اتاق
138
00:04:26,160 –> 00:04:29,520
دو نفر است، همچنین دو موقعیت است، این اتاق دو موقعیت با این دروازه فاصله دارد
139
00:04:29,520 –> 00:04:31,280
و ما درست ادامه می دهیم بگو خوب
140
00:04:31,280 –> 00:04:33,040
این اتاق سه است
141
00:04:33,040 –> 00:04:35,520
و از اینجا ادامه دهید این اتاق چهار است
142
00:04:35,520 –> 00:04:36,800
و از اینجا
143
00:04:36,800 –> 00:04:38,240
به طور مشابه درست می گوییم خوب این
144
00:04:38,240 –> 00:04:40,160
سه است این چهار است
145
00:04:40,160 –> 00:04:42,240
و این چهار درست است اما آیا
146
00:04:42,240 –> 00:04:43,680
واقعاً درست است که این اتاق
147
00:04:43,680 –> 00:04:45,919
چهار موقعیت دورتر است خوب ما فراموش کردیم
148
00:04:45,919 –> 00:04:46,960
این دروازه
149
00:04:46,960 –> 00:04:49,840
درست است راه دوم برای انجام این کار این
150
00:04:49,840 –> 00:04:50,919
است که
151
00:04:50,919 –> 00:04:54,160
همزمان یک bfs را از هر دو دروازه انجام دهیم،
152
00:04:54,160 –> 00:04:57,360
153
00:04:57,360 –> 00:04:58,880
بنابراین اگر زمانی
154
00:04:58,880 –> 00:05:00,560
به موقعیتی رسیدیم، بیایید
155
00:05:00,560 –> 00:05:02,720
ببینیم وقتی یک bfs را به طور همزمان انجام می دهیم چه اتفاقی می افتد،
156
00:05:02,720 –> 00:05:05,280
بنابراین از اینجا به سمت بگو این
157
00:05:05,280 –> 00:05:07,199
یکی است این دو یک موقعیت هستند و
158
00:05:07,199 –> 00:05:08,479
این نیز یک موقعیت است حالا
159
00:05:08,479 –> 00:05:10,320
از همه موقعیتهایمان میخواهیم
160
00:05:10,320 –> 00:05:12,000
bfs را درست ادامه دهیم، بنابراین
161
00:05:12,000 –> 00:05:14,479
از این یکی میگوییم این اتاقها
162
00:05:14,479 –> 00:05:16,240
دو اتاق با این یکی فاصله دارند. این
163
00:05:16,240 –> 00:05:16,720
اتاق
164
00:05:16,720 –> 00:05:19,759
در حال حاضر دو تا از این
165
00:05:19,759 –> 00:05:21,600
اتاق فاصله دارد، همین الان دو فاصله است، ما نمیخواهیم
166
00:05:21,600 –> 00:05:23,440
به این موقعیت برویم و بگوییم که
167
00:05:23,440 –> 00:05:25,440
سه موقعیت دورتر است زیرا با
168
00:05:25,440 –> 00:05:27,039
این که قبلاً بازدید شده است،
169
00:05:27,039 –> 00:05:29,120
ما قبلاً حداقل فاصله را پیدا کردهایم
170
00:05:29,120 –> 00:05:30,320
. دور
171
00:05:30,320 –> 00:05:33,280
از یک bfs درست، بنابراین هر بار که
172
00:05:33,280 –> 00:05:34,080
یک لایه را گسترش
173
00:05:34,080 –> 00:05:36,240
میدهیم، میگوییم خوب، اول بیایید
174
00:05:36,240 –> 00:05:37,280
همه اتاقها را در
175
00:05:37,280 –> 00:05:40,560
یک فاصله از یک دروازه پیدا کنیم، بعد
176
00:05:40,560 –> 00:05:40,960
177
00:05:40,960 –> 00:05:43,520
همه اتاقها را در فاصله دو فاصله از
178
00:05:43,520 –> 00:05:44,000
دروازه
179
00:05:44,000 –> 00:05:46,240
و سه قرار دهیم و این کار را ادامه میدهیم تا
180
00:05:46,240 –> 00:05:47,199
هر
181
00:05:47,199 –> 00:05:49,520
موقعیت واحد در شبکه ما دارای alr است به راحتی بازدید شده است
182
00:05:49,520 –> 00:05:50,880
یا
183
00:05:50,880 –> 00:05:52,560
اساسا نمی توانیم ادامه دهیم و می دانیم که
184
00:05:52,560 –> 00:05:54,880
راه حل های bfs با یک q پیاده سازی می شوند،
185
00:05:54,