{"id":349651,"date":"2023-07-01T15:00:59","date_gmt":"2023-07-01T15:00:59","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=349651"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=349651","title":{"rendered":"<span>\u0412\u043e\u043b\u043d\u043e\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/41d\/0c8\/5bd\/41d0c85bdfb2aa5f9e0263f0619d8e5f.png\" alt=\"\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 25\u00d725\" title=\"\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 25\u00d725\" width=\"876\" height=\"756\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/41d\/0c8\/5bd\/41d0c85bdfb2aa5f9e0263f0619d8e5f.png\"\/><\/p>\n<div><figcaption>\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 25\u00d725<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p><strong>\u0412\u043e\u043b\u043d\u043e\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/strong> \u2014 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u043e\u043b\u043d\u043e\u0432\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u043e \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u041d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0434\u0430\u043d\u043e \u043d\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e, \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044e \u0432\u043e\u043b\u043d\u044b, \u0432\u043e\u043b\u043d\u0430 \u043e\u0433\u0438\u0431\u0430\u0435\u0442 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f, \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044f \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e<\/p>\n<\/blockquote>\n<h2>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u044b \u0438 \u043f\u0435\u0449\u0435\u0440\u044b<\/h2>\n<details class=\"spoiler\">\n<summary>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u043e\u0432 \u0432 \u0444\u0430\u0439\u043b\u0435<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/c8c\/d2d\/63d\/c8cd2d63d4fa848ad6ff333311709d89.png\" alt=\"\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0444\u0430\u0439\u043b\u0435\" title=\"\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0444\u0430\u0439\u043b\u0435\" width=\"198\" height=\"521\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c8c\/d2d\/63d\/c8cd2d63d4fa848ad6ff333311709d89.png\"\/><\/p>\n<div><figcaption>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0444\u0430\u0439\u043b\u0435<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u2014 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0437\u0430\u043f\u0443\u0442\u0430\u043d\u043d\u044b\u0445 \u043f\u0443\u0442\u0435\u0439 \u043a \u0432\u044b\u0445\u043e\u0434\u0443.  <\/p>\n<\/blockquote>\n<ul>\n<li>\n<p>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0434\u0432\u0443\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u2014 \u043f\u0435\u0440\u0432\u0430\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0435\u043d\u044b \u0441\u043f\u0440\u0430\u0432\u0430, \u0432\u0442\u043e\u0440\u0430\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0435\u043d\u044b \u0441\u043d\u0438\u0437\u0443. (1 &#8212; \u0441\u0442\u0435\u043d\u0430 \u0435\u0441\u0442\u044c, 0 &#8212; \u0441\u0442\u0435\u043d\u044b \u043d\u0435\u0442)<\/p>\n<\/li>\n<li>\n<p>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0432\u0438\u0434\u0435 \u0434\u0432\u0443\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0432\u044b\u0434\u0435\u043b\u044f\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u0435\u0441\u043b\u0438 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0441\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0432 \u043e\u0434\u0438\u043d \u043c\u0430\u0441\u0441\u0438\u0432, \u0440\u0430\u0437\u043c\u0435\u0440 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u0441\u044f \u0434\u043e 20<strong>\u00d7<\/strong>20, \u0447\u0442\u043e \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 400 \u043a\u043b\u0435\u0442\u043e\u043a, \u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432\u0441\u0435\u0433\u043e 200 \u043a\u043b\u0435\u0442\u043e\u043a.<\/p>\n<\/li>\n<li>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u0442\u044c \u0438 \u043c\u0438\u043d\u0443\u0441\u044b, \u0442\u0430\u043a\u043e\u0439 \u0432\u0438\u0434 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043e\u0434\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0441 \u0434\u0432\u0443\u043c\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ab7\/350\/0d3\/ab73500d3d5d1529ee6848eabdb87fa4.png\" alt=\"\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435\" title=\"\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435\" width=\"622\" height=\"622\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ab7\/350\/0d3\/ab73500d3d5d1529ee6848eabdb87fa4.png\"\/><\/p>\n<div><figcaption>\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435<\/figcaption><\/div>\n<\/figure>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/7f0\/b9f\/e21\/7f0b9fe21c8d8af23ec22db25f15a3dd.png\" alt=\"\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435\" title=\"\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435\" width=\"192\" height=\"261\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7f0\/b9f\/e21\/7f0b9fe21c8d8af23ec22db25f15a3dd.png\"\/><\/p>\n<div><figcaption>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435<\/figcaption><\/div>\n<\/figure>\n<ul>\n<li>\n<p>\u041f\u0435\u0449\u0435\u0440\u0430 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435 \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b, \u043a\u0430\u0436\u0434\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u0442\u043e\u043c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043e\u043d\u0430 \u0441\u0442\u0435\u043d\u043e\u0439 \u0438\u043b\u0438 \u043f\u0443\u0441\u0442\u043e\u0442\u043e\u0439. (1 &#8212; \u0441\u0442\u0435\u043d\u0430, 0 &#8212; \u043f\u0443\u0441\u0442\u043e\u0442\u0430)<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u043e \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u0435\u0449\u0435\u0440 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u043c\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435:<br \/><a href=\"https:\/\/habr.com\/ru\/articles\/741564\/\" rel=\"noopener noreferrer nofollow\">\u0413\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0435\u0449\u0435\u0440 by tonitaga<\/a><\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/2d7\/b72\/4ee\/2d7b724ee618e66097ccfc29b1aaf672.png\" alt=\"\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u0435\u0449\u0435\u0440\u0430 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435\" title=\"\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u0435\u0449\u0435\u0440\u0430 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435\" width=\"622\" height=\"622\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2d7\/b72\/4ee\/2d7b724ee618e66097ccfc29b1aaf672.png\"\/><\/p>\n<div><figcaption>\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u0435\u0449\u0435\u0440\u0430 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435<\/figcaption><\/div>\n<\/figure>\n<\/div>\n<\/details>\n<h2>\u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u043e\u043b\u043d\u043e\u0432\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h2>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u043e \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430 <\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/b3c\/8cf\/51c\/b3c8cf51ccfcea16b1a1a695f7aadc50.png\" alt=\"\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430\" title=\"\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430\" width=\"342\" height=\"343\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b3c\/8cf\/51c\/b3c8cf51ccfcea16b1a1a695f7aadc50.png\"\/><\/p>\n<div><figcaption>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p><strong>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/strong> \u2014\u00a0\u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u043e\u0441\u0442\u044c \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u0430\u0440\u043a\u0435\u0442\u0435, \u0438\u043c\u0435\u044e\u0449\u0438\u0445 \u043e\u0431\u0449\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u043e\u0439.<\/p>\n<\/blockquote>\n<\/div>\n<\/details>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u041c\u0443\u0440\u0430, \u043e\u0434\u043d\u0430\u043a\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u043e\u043c \u044d\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u0430, \u043a\u0430\u043a \u0438 \u0432 \u0436\u0438\u0437\u043d\u0438, \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0433\u0434\u0435 \u043d\u0435\u0442 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u0432\u043e\u043b\u043d\u043e\u0439 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u043b\u0438\u0431\u043e \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442 \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e.<\/p>\n<\/li>\n<\/ul>\n<h2>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 \u0421++<\/h2>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u043f\u0435\u0449\u0435\u0440\u0435<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>\u0412 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 (\u043c\u0430\u0441\u0441\u0438\u0432) \u0434\u043b\u0438\u043d, \u0433\u0434\u0435 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0442 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u0434\u043e \u043a\u043b\u0435\u0442\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">CaveWrapper length_map;<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 CaveWrapper?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>CaveWrapper \u2014 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c \u043a\u0430\u043a \u0441 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0437\u043d\u0430\u0435\u0442 \u0432 \u0432\u0430\u043b\u0438\u0434\u043d\u043e\u043c \u043b\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u0435\u0449\u0435\u0440\u0430 \u0438  \u0437\u043d\u0430\u0435\u0442 \u0435\u0451 \u0440\u0430\u0437\u043c\u0435\u0440\u044b<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">  template &lt;>   struct BasicWrapper&lt;kCave> final {     using data_type = std::vector&lt;size_type>;          data_type data;     size_type rows = 0, cols = 0;      bool IsGood() const {         \/\/ Some checks     }      size_type &amp;operator()(size_type row, size_type col) {         return data[row * cols + col];     }      size_type operator()(size_type row, size_type col) const {         return data[row * cols + col];     } };  using CaveWrapper = BasicWrapper&lt;kCave>;<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u0412\u043e \u0432\u0442\u043e\u0440\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u043e\u043b\u043d\u044b. \u0412\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d\u044b \u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435, \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u0432\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">std::vector&lt;Point> wave, old_wave;<\/code><\/pre>\n<ul>\n<li>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0437\u043d\u0430\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0432\u043e\u043b\u043d\u0430 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u043b\u0430\u0441\u044c<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">size_type wave_step = 0;<\/code><\/pre>\n<h2>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n<ul>\n<li>\n<p>\u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043c\u044b \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438<\/p>\n<\/li>\n<li>\n<p>\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0434\u043b\u0438\u043d (length_map) \u2014 \u044d\u0442\u043e \u0441\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u0432 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043f\u043e \u043d\u0435\u043c\u0443 \u043c\u044b \u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c. \u0423 \u044d\u0442\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435\u0433\u043e \u0434\u0432\u0430 \u0442\u0438\u043f\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439: -1 (\u0415\u0441\u043b\u0438 \u0432\u043e\u043b\u043d\u0430 \u0435\u0449\u0435 \u043d\u0435 \u0431\u044b\u043b\u0430 \u0432 \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435) \u0438 &#171;\u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e&#187; &#8212; \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0442\u0435\u043a\u0443\u0449\u0435\u0439.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">void InitializeStartState(const CaveWrapper &amp;cave, Point from) {     old_wave = {from};     length_map = {CaveWrapper::data_type(cave.rows * cave.cols, -1), cave.rows, cave.cols};     length_map(from.x, from.y) = 0; }<\/code><\/pre>\n<ul>\n<li>\n<p>\u041a\u043b\u0435\u0442\u043a\u0430 \u0441\u0442\u0430\u0440\u0442\u0430 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u0430 \u043a\u0430\u043a 0, \u0442\u0430\u043a \u043a\u0430\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0438 \u0435\u0441\u0442\u044c 0. \u041e\u0442 \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0438 \u043d\u0430\u0447\u043d\u0435\u0442\u0441\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d\u044b.<\/p>\n<\/li>\n<li>\n<p>old_wave \u0431\u0443\u0434\u0435\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0430\u0440\u0442\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0432\u043e\u043b\u043d\u044b \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u0438\u043c\u0435\u043d\u043d\u043e \u043e\u0442 \u044d\u0442\u043e\u0439 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430<\/h2>\n<ul>\n<li>\n<p>\u041f\u043e\u0432\u0442\u043e\u0440\u044e\u0441\u044c, \u043d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430 (wave) \u0431\u0443\u0434\u0435\u0442 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0441\u0442\u0430\u0440\u043e\u0439 \u0432\u043e\u043b\u043d\u044b (old_wave). <\/p>\n<\/li>\n<li>\n<p>\u0421\u0442\u0430\u0440\u0430\u044f \u0432\u043e\u043b\u043d\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u043b\u0438\u0448\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438 \u043d\u0443\u0436\u043d\u043e \u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043d\u043e\u0432\u0443\u044e \u0432\u043e\u043b\u043d\u0443<\/p>\n<\/li>\n<li>\n<p>\u0417\u043d\u0430\u044f \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f (old_wave), \u0431\u0443\u0434\u0435\u0442 \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c \u0432\u043e\u043b\u043d\u0443 \u0434\u0430\u043b\u044c\u0448\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">bool StepWave(const CaveWrapper &amp;cave, Point to) {   ++wave_step;   for (auto [row, col] : old_wave) {     for (auto [x, y, value] : {SidePoint{row + 1, col, cave(row + 1, col)},                                SidePoint{row - 1, col, cave(row - 1, col)},                                SidePoint{row, col + 1, cave(row, col + 1)},                                SidePoint{row, col - 1, cave(row, col - 1)}}) {       if (value == 0) {         if (length_map_(x, y) == -1) {           wave.emplace_back(x, y);           length_map(x, y) = wave_step;         }          if (x == to.x and y == to.y)           return true;       }     }   }   old_wave = std::move(wave);   return false; }<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 SidePoint?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>SidePoint \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0441\u0435\u0431\u0435 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0438 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/p>\n<\/li>\n<li>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u0417\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0432\u043e\u043b\u043d\u044b \u043c\u044b \u0432\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435 \u043c\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0438 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f value \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0437\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u0438 \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u044d\u0442\u0430\u043f\u043e\u043c \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0431\u044b\u043b\u0430 \u043b\u0438 \u0432\u043e\u043b\u043d\u0430 \u0443\u0436\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0442\u043e\u0447\u043a\u0435, \u0438 \u0435\u0441\u043b\u0438 \u0432\u043e\u043b\u043d\u044b \u0442\u0430\u043c \u0435\u0449\u0435 \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043c\u044b \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0432\u043e\u043b\u043d\u0443 \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u043f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0438 \u043c\u044b \u043a\u043e\u043d\u0446\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0430 \u0444\u0438\u043d\u0438\u0448\u0430 (Point to)<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0431\u044b\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u043d\u044b \u0438 \u0432\u043e\u043b\u043d\u0430 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u043c\u044b \u0432 \u0441\u0442\u0430\u0440\u0443\u044e \u0432\u043e\u043b\u043d\u0443 \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f. (19 \u0441\u0442\u0440\u043e\u0447\u043a\u0430).<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438<\/h2>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u043e\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0432\u0441\u0435 \u043f\u0443\u0442\u0438 \u0441\u0440\u0430\u0437\u0443, \u043d\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0438\u043c\u0435\u043d\u043d\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0435\u0433\u043e, \u0442\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e \u0432\u0435\u0440\u043d\u0443\u0442\u044c\u0441\u044f \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0432 \u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0430\u0440\u0442\u0430, \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0434\u043b\u0438\u043d.<\/p>\n<\/li>\n<li>\n<p>\u0417\u043d\u0430\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c \u043a\u0443\u0434\u0430 \u043d\u0430\u043c \u0438\u0434\u0442\u0438 (\u0432\u0432\u0435\u0440\u0445, \u0432\u043d\u0438\u0437, \u0432\u043f\u0440\u0430\u0432\u043e, \u0432\u043b\u0435\u0432\u043e), \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0438 \u043a\u043b\u0435\u0442\u043a\u0438 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0438 \u0435\u0441\u043b\u0438 \u043a\u043b\u0435\u0442\u043a\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u043c\u0435\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043d\u0430 1, \u0442\u043e \u044d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043d\u0430\u0448 \u043f\u0443\u0442\u044c.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u043f\u043e\u043a\u0430 \u043d\u0435 \u0434\u043e\u0439\u0434\u0435\u043c \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (\u0432\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u043c\u044b \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043b\u0438 \u043d\u0443\u043b\u0435\u043c)<\/p>\n<\/li>\n<\/ul>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/85f\/e3e\/55b\/85fe3e55b9dfecc9624440743955dc1b.png\" alt=\"\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\" title=\"\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\" width=\"336\" height=\"301\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/85f\/e3e\/55b\/85fe3e55b9dfecc9624440743955dc1b.png\"\/><\/p>\n<div><figcaption>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)<\/figcaption><\/div>\n<\/figure>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u043e \u043d\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c, \u043d\u043e \u043c\u044b \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u043c\u043d\u043e\u0433\u0438\u0445<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">std::vector&lt;Point> MakePath(const CaveWrapper &amp;cave, Point from, Point to){   std::vector&lt;Point> path{to};   auto &amp;[row, col] = to;   while (length_map_(row, col) != 0) {     \/\/ TOP     if (length_map_(row + 1, col) + 1 == length_map_(row, col) and cave(row + 1, col) == 0)       ++row;     \/\/ BOTTOM     else if (length_map_(row - 1, col) + 1 == length_map_(row, col) and cave(row - 1, col) == 0)       --row;     \/\/ RIGTH     else if (length_map_(row, col + 1) + 1 == length_map_(row, col) and cave(row, col + 1) == 0)       ++col;     \/\/ LEFT     else if (length_map_(row, col - 1) + 1 == length_map_(row, col) and cave(row, col - 1) == 0)       --col;     else       return {}; \/\/ \u0415\u0441\u043b\u0438 \u043d\u0435\u043a\u0443\u0434\u0430 \u0438\u0434\u0442\u0438, \u0437\u043d\u0430\u0447\u0438\u0442 \u043f\u0443\u0442\u0438 \u043d\u0435\u0442     path.emplace_back(to);   }   path.back() = from;   return path; }<\/code><\/pre>\n<h2>\u041e\u0431\u0449\u0438\u0439 \u0432\u0438\u0434 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/h2>\n<pre><code class=\"cpp\">std::vector&lt;Point> Solve(const CaveWrapper &amp;cave, Point from, Point to) &amp; {   if (!cave.IsGood() or cave(from.x, from.y) == 1 or cave(to.x, to.y) == 1)     return {};      InitializeStartState(cave, from);   while (!old_wave_.empty()) {     if (StepWave(cave, to))       break;   }    return MakePath(cave, from, to); }<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043b\u0438\u0448\u044c \u0442\u0435\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u0441 \u043e\u0434\u043d\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c, \u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0441 \u0434\u0432\u0443\u043c\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438. \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0438\u0447\u0435\u043c \u043d\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0433\u043b\u0430\u0432\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u044c \u043d\u0435 \u043f\u0435\u0449\u0435\u0440\u0430 \u0430 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0442\u0438\u043f \u0434\u0430\u043d\u043d\u044b\u0445 \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e MazeWrapper<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 MazeWrapper?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>MazeWrapper \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u0432 \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c \u043a\u0430\u043a \u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c, \u0432\u0441\u0435 \u044d\u0442\u043e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u043f\u0435\u0440\u0435\u0433\u0440\u0443\u0436\u0435\u043d\u043d\u043e\u043c\u0443 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0443 \u043a\u0440\u0443\u0433\u043b\u044b\u0445 \u0441\u043a\u043e\u0431\u043e\u0447\u0435\u043a<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">template &lt;> struct BasicWrapper&lt;kMaze> final {   using data_type = std::vector&lt;size_type>;    data_type right, bottom;   size_type rows = 0, cols = 0;    bool IsGood() const {     \/\/ Some checks   }    size_type &amp;operator()(size_type row, size_type col, bool is_right = true) {     return is_right ? right[row * cols + col] : bottom[row * cols + col];   }    size_type operator()(size_type row, size_type col, bool is_right = true) const {     return is_right ? right[row * cols + col] : bottom[row * cols + col];   } };  using MazeWrapper = BasicWrapper&lt;kMaze>;<\/code><\/pre>\n<ul>\n<li>\n<p>\u0418\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e \u0447\u0442\u043e \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442 \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0432 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0435 \u043a\u0440\u0443\u0433\u043b\u044b\u0445 \u0441\u043a\u043e\u0431\u043e\u043a \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d bool \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0432\u043d\u0435 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0438 \u043f\u0440\u0438 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 (\u0432\u0441\u0435 \u044d\u0442\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u0442\u0435\u043c \u043a\u0430\u043a \u044d\u0442\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435)<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430<\/h2>\n<pre><code class=\"cpp\">bool StepWave(const MazeWrapper &amp;maze, Point to) {   ++wave_step;   for (auto [row, col] : old_wave) {     for (auto [x, y, value] : {SidePoint{row + 1, col, maze(row, col, false)},                                SidePoint{row - 1, col, maze(row - 1, col, false)},                                SidePoint{row, col + 1, maze(row, col)},                                SidePoint{row, col - 1, maze(row, col - 1)}}) {       if (value == 0) {         if (length_map(x, y) == -1) {           wave.emplace_back(x, y);           length_map(x, y) = wave_step;         }          if (x == to.x and y == to.y)           return true;       }     }   }   old_wave = std::move(wave);   return false; }<\/code><\/pre>\n<h2>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438<\/h2>\n<ul>\n<li>\n<p>\u0412 \u043c\u043e\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u042d\u043b\u043b\u0435\u0440\u0430, \u044d\u0442\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435 \u043e\u0442 \u043b\u044e\u0431\u044b\u0445 \u0434\u0432\u0443\u0445 \u0442\u043e\u0447\u0435\u043a \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u043f\u0443\u0442\u044c, \u0435\u0433\u043e \u043c\u044b \u0438 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c.<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043b\u0435\u0437\u043d\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u042d\u043b\u043b\u0435\u0440\u0430<br \/><a href=\"https:\/\/habr.com\/ru\/articles\/667576\/\" rel=\"noopener noreferrer nofollow\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u042d\u043b\u043b\u0435\u0440\u0430<\/a><\/p>\n<\/li>\n<\/ul>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/9b2\/a28\/614\/9b2a28614ba052e86df47eb1481ab85a.png\" alt=\"\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\" title=\"\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\" width=\"342\" height=\"297\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9b2\/a28\/614\/9b2a28614ba052e86df47eb1481ab85a.png\"\/><\/p>\n<div><figcaption>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)<\/figcaption><\/div>\n<\/figure>\n<ul>\n<li>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c \u0447\u0442\u043e \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c 20 \u0435\u0441\u0442\u044c \u043a\u043b\u0435\u0442\u043a\u0430 19, \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0432 \u044d\u0442\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u043e\u0434\u043d\u0430\u043a\u043e \u0442\u0430\u043c \u0441\u0442\u0435\u043d\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0435\u0440\u0435\u0434 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u043e\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u043d\u0435\u0442 \u043b\u0438 \u0441\u0442\u0435\u043d\u043a\u0438 \u0442\u0430\u043c, \u043a\u0443\u0434\u0430 \u043c\u044b \u043f\u043e\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0435\u043c. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u043e, \u043f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u043a\u0432\u043e\u0437\u044c \u0441\u0442\u0435\u043d\u044b \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430, \u0447\u0442\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0432\u0435\u0440\u043d\u044b\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">std::vector&lt;Point> MakePath(const MazeWrapper &amp;maze, Point from, Point to){   std::vector&lt;Point> path{to};   auto &amp;[row, col] = to;   while (length_map_(row, col) != 0) {     \/\/ LEFT     if (length_map_(row, col - 1) + 1 == length_map_(row, col) and maze(row, col - 1) == 0)       --col;     \/\/ RIGHT     else if (length_map_(row, col + 1) + 1 == length_map_(row, col) and maze(row, col) == 0)       ++col;     \/\/ BOTTOM     else if (length_map_(row - 1, col) + 1 == length_map_(row, col) and maze(row - 1, col, false) == 0)       --row;     \/\/ TOP     else if (length_map_(row + 1, col) + 1 == length_map_(row, col) and maze(row, col, false) == 0)       ++row;     else       return {}; \/\/ \u0415\u0441\u043b\u0438 \u043d\u0435\u043a\u0443\u0434\u0430 \u0438\u0434\u0442\u0438, \u0437\u043d\u0430\u0447\u0438\u0442 \u043f\u0443\u0442\u0438 \u043d\u0435\u0442     path.emplace_back(to);   }   path.back() = from;   return path; }<\/code><\/pre>\n<h2>\u041e\u0431\u0449\u0438\u0439 \u0432\u0438\u0434 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/h2>\n<pre><code class=\"cpp\">std::vector&lt;Point> Solve(const MazeWrapper &amp;maze, Point from, Point to) &amp; {   if (!maze.IsGood())     return {};   InitializeStartState(maze, from);   while (!old_wave_.empty())     if (StepWave(maze, to))       break;    return MakePath(maze, from, to); }<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<h2>\u041f\u043e\u043b\u0435\u0437\u043d\u044b\u0435 \u0441\u0441\u044b\u043b\u043a\u0438<\/h2>\n<ul>\n<li>\n<p>\u0425\u043e\u0447\u0443 \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0441\u0432\u043e\u0438\u043c github&#8217;\u043e\u043c, \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0437\u043d\u0430\u0442\u0435\u043b\u0435\u043d \u0435\u0441\u043b\u0438 \u0432\u044b \u043e\u0444\u043e\u0440\u043c\u0438\u0442\u0435 \u043f\u043e\u0434\u043f\u0438\u0441\u043a\u0443:<br \/><a href=\"https:\/\/github.com\/tonitaga\" rel=\"noopener noreferrer nofollow\">GitHub<\/a><\/p>\n<\/li>\n<li>\n<p>\u0421\u0442\u0430\u0442\u044c\u044f, \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u0430\u044f \u043c\u043d\u043e\u0439, \u043f\u043e \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0435\u0449\u0435\u0440:<br \/><a href=\"https:\/\/habr.com\/ru\/articles\/741564\/\" rel=\"noopener noreferrer nofollow\">\u0413\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0435\u0449\u0435\u0440<\/a><\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043b\u0435\u0437\u043d\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430:<br \/><a href=\"https:\/\/habr.com\/ru\/articles\/667576\/\" rel=\"noopener noreferrer nofollow\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u042d\u043b\u043b\u0435\u0440\u0430<\/a><\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u044b \u043f\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043f\u0438\u0448\u0438\u0442\u0435 \u0432 \u0442\u0435\u043b\u0435\u0433\u0440\u0430\u043c:<br \/><a class=\"mention\" href=\"\/users\/tonitaga\">@tonitaga<\/a><\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p> <!----> <!----><\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/745294\/\"> https:\/\/habr.com\/ru\/articles\/745294\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\">\n<div><figcaption>\u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 25\u00d725<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p><strong>\u0412\u043e\u043b\u043d\u043e\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/strong> \u2014 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0443\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u043e\u043b\u043d\u043e\u0432\u043e\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u043e \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.<\/p>\n<p>\u041d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0434\u0430\u043d\u043e \u043d\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e, \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044e \u0432\u043e\u043b\u043d\u044b, \u0432\u043e\u043b\u043d\u0430 \u043e\u0433\u0438\u0431\u0430\u0435\u0442 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f, \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044f \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e<\/p>\n<\/blockquote>\n<h2>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u044b \u0438 \u043f\u0435\u0449\u0435\u0440\u044b<\/h2>\n<details class=\"spoiler\">\n<summary>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u043e\u0432 \u0432 \u0444\u0430\u0439\u043b\u0435<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\">\n<div><figcaption>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0444\u0430\u0439\u043b\u0435<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u2014 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0437\u0430\u043f\u0443\u0442\u0430\u043d\u043d\u044b\u0445 \u043f\u0443\u0442\u0435\u0439 \u043a \u0432\u044b\u0445\u043e\u0434\u0443.  <\/p>\n<\/blockquote>\n<ul>\n<li>\n<p>\u041b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0434\u0432\u0443\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u2014 \u043f\u0435\u0440\u0432\u0430\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0435\u043d\u044b \u0441\u043f\u0440\u0430\u0432\u0430, \u0432\u0442\u043e\u0440\u0430\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0435\u043d\u044b \u0441\u043d\u0438\u0437\u0443. (1 &#8212; \u0441\u0442\u0435\u043d\u0430 \u0435\u0441\u0442\u044c, 0 &#8212; \u0441\u0442\u0435\u043d\u044b \u043d\u0435\u0442)<\/p>\n<\/li>\n<li>\n<p>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0432 \u0432\u0438\u0434\u0435 \u0434\u0432\u0443\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0432\u044b\u0434\u0435\u043b\u044f\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u0435\u0441\u043b\u0438 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0432\u0441\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0432 \u043e\u0434\u0438\u043d \u043c\u0430\u0441\u0441\u0438\u0432, \u0440\u0430\u0437\u043c\u0435\u0440 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u0441\u044f \u0434\u043e 20<strong>\u00d7<\/strong>20, \u0447\u0442\u043e \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 400 \u043a\u043b\u0435\u0442\u043e\u043a, \u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432\u0441\u0435\u0433\u043e 200 \u043a\u043b\u0435\u0442\u043e\u043a.<\/p>\n<\/li>\n<li>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u0442\u044c \u0438 \u043c\u0438\u043d\u0443\u0441\u044b, \u0442\u0430\u043a\u043e\u0439 \u0432\u0438\u0434 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u043e\u0434\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0441 \u0434\u0432\u0443\u043c\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\">\n<div><figcaption>\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435<\/figcaption><\/div>\n<\/figure>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\">\n<div><figcaption>\u0425\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0432 \u0444\u0430\u0439\u043b\u0435<\/figcaption><\/div>\n<\/figure>\n<ul>\n<li>\n<p>\u041f\u0435\u0449\u0435\u0440\u0430 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0444\u0430\u0439\u043b\u0435 \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b, \u043a\u0430\u0436\u0434\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043e \u0442\u043e\u043c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043e\u043d\u0430 \u0441\u0442\u0435\u043d\u043e\u0439 \u0438\u043b\u0438 \u043f\u0443\u0441\u0442\u043e\u0442\u043e\u0439. (1 &#8212; \u0441\u0442\u0435\u043d\u0430, 0 &#8212; \u043f\u0443\u0441\u0442\u043e\u0442\u0430)<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u043e \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u0435\u0449\u0435\u0440 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u043c\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435:<br \/><a href=\"https:\/\/habr.com\/ru\/articles\/741564\/\" rel=\"noopener noreferrer nofollow\">\u0413\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0435\u0449\u0435\u0440 by tonitaga<\/a><\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\">\n<div><figcaption>\u041e\u0442\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043f\u0435\u0449\u0435\u0440\u0430 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435<\/figcaption><\/div>\n<\/figure>\n<\/div>\n<\/details>\n<h2>\u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u043e\u043b\u043d\u043e\u0432\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h2>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u043e \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430 <\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"\">\n<div><figcaption>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/figcaption><\/div>\n<\/figure>\n<blockquote>\n<p><strong>\u041e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/strong> \u2014\u00a0\u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u043e\u0441\u0442\u044c \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u0430\u0440\u043a\u0435\u0442\u0435, \u0438\u043c\u0435\u044e\u0449\u0438\u0445 \u043e\u0431\u0449\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u043e\u0439.<\/p>\n<\/blockquote>\n<\/div>\n<\/details>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u041c\u0443\u0440\u0430, \u043e\u0434\u043d\u0430\u043a\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u043e\u043c \u044d\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u0430, \u043a\u0430\u043a \u0438 \u0432 \u0436\u0438\u0437\u043d\u0438, \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u0443 \u0441\u0442\u043e\u0440\u043e\u043d\u0443, \u0433\u0434\u0435 \u043d\u0435\u0442 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u0432\u043e\u043b\u043d\u043e\u0439 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u043b\u0438\u0431\u043e \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442 \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e.<\/p>\n<\/li>\n<\/ul>\n<h2>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 \u0421++<\/h2>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u043f\u0435\u0449\u0435\u0440\u0435<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>\u0412 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 (\u043c\u0430\u0441\u0441\u0438\u0432) \u0434\u043b\u0438\u043d, \u0433\u0434\u0435 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0442 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u0442\u0430\u0440\u0442\u0430 \u0434\u043e \u043a\u043b\u0435\u0442\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">CaveWrapper length_map;<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 CaveWrapper?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>CaveWrapper \u2014 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c \u043a\u0430\u043a \u0441 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0437\u043d\u0430\u0435\u0442 \u0432 \u0432\u0430\u043b\u0438\u0434\u043d\u043e\u043c \u043b\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u0435\u0449\u0435\u0440\u0430 \u0438  \u0437\u043d\u0430\u0435\u0442 \u0435\u0451 \u0440\u0430\u0437\u043c\u0435\u0440\u044b<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">  template &lt;>   struct BasicWrapper&lt;kCave> final {     using data_type = std::vector&lt;size_type>;          data_type data;     size_type rows = 0, cols = 0;      bool IsGood() const {         \/\/ Some checks     }      size_type &amp;operator()(size_type row, size_type col) {         return data[row * cols + col];     }      size_type operator()(size_type row, size_type col) const {         return data[row * cols + col];     } };  using CaveWrapper = BasicWrapper&lt;kCave>;<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u0412\u043e \u0432\u0442\u043e\u0440\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u043e\u043b\u043d\u044b. \u0412\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d\u044b \u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435, \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u0432\u043e\u043b\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">std::vector&lt;Point> wave, old_wave;<\/code><\/pre>\n<ul>\n<li>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0437\u043d\u0430\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0432\u043e\u043b\u043d\u0430 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0438\u043b\u0430\u0441\u044c<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">size_type wave_step = 0;<\/code><\/pre>\n<h2>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n<ul>\n<li>\n<p>\u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043c\u044b \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438<\/p>\n<\/li>\n<li>\n<p>\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0434\u043b\u0438\u043d (length_map) \u2014 \u044d\u0442\u043e \u0441\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u0432 \u044d\u0442\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043f\u043e \u043d\u0435\u043c\u0443 \u043c\u044b \u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c. \u0423 \u044d\u0442\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0431\u0443\u0434\u0435\u0442 \u0432\u0441\u0435\u0433\u043e \u0434\u0432\u0430 \u0442\u0438\u043f\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439: -1 (\u0415\u0441\u043b\u0438 \u0432\u043e\u043b\u043d\u0430 \u0435\u0449\u0435 \u043d\u0435 \u0431\u044b\u043b\u0430 \u0432 \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435) \u0438 &#171;\u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e&#187; &#8212; \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0434\u043e \u0442\u0435\u043a\u0443\u0449\u0435\u0439.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">void InitializeStartState(const CaveWrapper &amp;cave, Point from) {     old_wave = {from};     length_map = {CaveWrapper::data_type(cave.rows * cave.cols, -1), cave.rows, cave.cols};     length_map(from.x, from.y) = 0; }<\/code><\/pre>\n<ul>\n<li>\n<p>\u041a\u043b\u0435\u0442\u043a\u0430 \u0441\u0442\u0430\u0440\u0442\u0430 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u0430 \u043a\u0430\u043a 0, \u0442\u0430\u043a \u043a\u0430\u043a \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0438 \u0435\u0441\u0442\u044c 0. \u041e\u0442 \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0438 \u043d\u0430\u0447\u043d\u0435\u0442\u0441\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u0435 \u0432\u043e\u043b\u043d\u044b.<\/p>\n<\/li>\n<li>\n<p>old_wave \u0431\u0443\u0434\u0435\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0430\u0440\u0442\u0430, \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0432\u043e\u043b\u043d\u044b \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u0438\u043c\u0435\u043d\u043d\u043e \u043e\u0442 \u044d\u0442\u043e\u0439 \u0442\u043e\u0447\u043a\u0438.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430<\/h2>\n<ul>\n<li>\n<p>\u041f\u043e\u0432\u0442\u043e\u0440\u044e\u0441\u044c, \u043d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430 (wave) \u0431\u0443\u0434\u0435\u0442 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0441\u0442\u0430\u0440\u043e\u0439 \u0432\u043e\u043b\u043d\u044b (old_wave). <\/p>\n<\/li>\n<li>\n<p>\u0421\u0442\u0430\u0440\u0430\u044f \u0432\u043e\u043b\u043d\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u043b\u0438\u0448\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438 \u043d\u0443\u0436\u043d\u043e \u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043d\u043e\u0432\u0443\u044e \u0432\u043e\u043b\u043d\u0443<\/p>\n<\/li>\n<li>\n<p>\u0417\u043d\u0430\u044f \u043c\u0430\u0441\u0441\u0438\u0432 \u0442\u043e\u0447\u0435\u043a \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f (old_wave), \u0431\u0443\u0434\u0435\u0442 \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0442\u044c \u0432\u043e\u043b\u043d\u0443 \u0434\u0430\u043b\u044c\u0448\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u044c \u0444\u043e\u043d \u041d\u0435\u0439\u043c\u0430\u043d\u0430<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">bool StepWave(const CaveWrapper &amp;cave, Point to) {   ++wave_step;   for (auto [row, col] : old_wave) {     for (auto [x, y, value] : {SidePoint{row + 1, col, cave(row + 1, col)},                                SidePoint{row - 1, col, cave(row - 1, col)},                                SidePoint{row, col + 1, cave(row, col + 1)},                                SidePoint{row, col - 1, cave(row, col - 1)}}) {       if (value == 0) {         if (length_map_(x, y) == -1) {           wave.emplace_back(x, y);           length_map(x, y) = wave_step;         }          if (x == to.x and y == to.y)           return true;       }     }   }   old_wave = std::move(wave);   return false; }<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 SidePoint?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>SidePoint \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0441\u0435\u0431\u0435 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0438 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<\/p>\n<\/li>\n<li>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u0417\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0432\u043e\u043b\u043d\u044b \u043c\u044b \u0432\u043e \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435 \u043c\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0442\u043e\u0447\u043a\u0438 \u0438 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f value \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0437\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u0438 \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u0438\u044f \u043d\u0435\u0442, \u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u044d\u0442\u0430\u043f\u043e\u043c \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0431\u044b\u043b\u0430 \u043b\u0438 \u0432\u043e\u043b\u043d\u0430 \u0443\u0436\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0442\u043e\u0447\u043a\u0435, \u0438 \u0435\u0441\u043b\u0438 \u0432\u043e\u043b\u043d\u044b \u0442\u0430\u043c \u0435\u0449\u0435 \u043d\u0435 \u0431\u044b\u043b\u043e, \u0442\u043e \u043c\u044b \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u044f\u0435\u043c \u043d\u043e\u0432\u0443\u044e \u0432\u043e\u043b\u043d\u0443 \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u043f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0438 \u043c\u044b \u043a\u043e\u043d\u0446\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0430 \u0444\u0438\u043d\u0438\u0448\u0430 (Point to)<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0431\u044b\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u043d\u044b \u0438 \u0432\u043e\u043b\u043d\u0430 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043b\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438, \u043c\u044b \u0432 \u0441\u0442\u0430\u0440\u0443\u044e \u0432\u043e\u043b\u043d\u0443 \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f. (19 \u0441\u0442\u0440\u043e\u0447\u043a\u0430).<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438<\/h2>\n<ul>\n<li>\n<p>\u0412\u043e\u043b\u043d\u043e\u0432\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0432\u0441\u0435 \u043f\u0443\u0442\u0438 \u0441\u0440\u0430\u0437\u0443, \u043d\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0438\u043c\u0435\u043d\u043d\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0435\u0433\u043e, \u0442\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e \u0432\u0435\u0440\u043d\u0443\u0442\u044c\u0441\u044f \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0432 \u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0430\u0440\u0442\u0430, \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0434\u043b\u0438\u043d.<\/p>\n<\/li>\n<li>\n<p>\u0417\u043d\u0430\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c \u043a\u0443\u0434\u0430 \u043d\u0430\u043c \u0438\u0434\u0442\u0438 (\u0432\u0432\u0435\u0440\u0445, \u0432\u043d\u0438\u0437, \u0432\u043f\u0440\u0430\u0432\u043e, \u0432\u043b\u0435\u0432\u043e), \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0438 \u043a\u043b\u0435\u0442\u043a\u0438 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0438 \u0435\u0441\u043b\u0438 \u043a\u043b\u0435\u0442\u043a\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u043c\u0435\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043d\u0430 1, \u0442\u043e \u044d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u043d\u0430\u0448 \u043f\u0443\u0442\u044c.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0443\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u043f\u043e\u043a\u0430 \u043d\u0435 \u0434\u043e\u0439\u0434\u0435\u043c \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (\u0432\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0434\u043b\u0438\u043d \u043c\u044b \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043b\u0438 \u043d\u0443\u043b\u0435\u043c)<\/p>\n<\/li>\n<\/ul>\n<figure class=\"\">\n<div><figcaption>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)<\/figcaption><\/div>\n<\/figure>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0443\u0442\u0438 \u043e\u0442 \u0442\u043e\u0447\u043a\u0438 \u0444\u0438\u043d\u0438\u0448\u0430 \u0434\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 (length_map)\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u043e \u043d\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c, \u043d\u043e \u043c\u044b \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u043c\u043d\u043e\u0433\u0438\u0445<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">std::vector&lt;Point> MakePath(const CaveWrapper &amp;cave, Point from, Point to){   std::vector&lt;Point> path{to};   auto &amp;[row, col] = to;   while (length_map_(row, col) != 0) {     \/\/ TOP     if (length_map_(row + 1, col) + 1 == length_map_(row, col) and cave(row + 1, col) == 0)       ++row;     \/\/ BOTTOM     else if (length_map_(row - 1, col) + 1 == length_map_(row, col) and cave(row - 1, col) == 0)       --row;     \/\/ RIGTH     else if (length_map_(row, col + 1) + 1 == length_map_(row, col) and cave(row, col + 1) == 0)       ++col;     \/\/ LEFT     else if (length_map_(row, col - 1) + 1 == length_map_(row, col) and cave(row, col - 1) == 0)       --col;     else       return {}; \/\/ \u0415\u0441\u043b\u0438 \u043d\u0435\u043a\u0443\u0434\u0430 \u0438\u0434\u0442\u0438, \u0437\u043d\u0430\u0447\u0438\u0442 \u043f\u0443\u0442\u0438 \u043d\u0435\u0442     path.emplace_back(to);   }   path.back() = from;   return path; }<\/code><\/pre>\n<h2>\u041e\u0431\u0449\u0438\u0439 \u0432\u0438\u0434 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/h2>\n<pre><code class=\"cpp\">std::vector&lt;Point> Solve(const CaveWrapper &amp;cave, Point from, Point to) &amp; {   if (!cave.IsGood() or cave(from.x, from.y) == 1 or cave(to.x, to.y) == 1)     return {};      InitializeStartState(cave, from);   while (!old_wave_.empty()) {     if (StepWave(cave, to))       break;   }    return MakePath(cave, from, to); }<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043b\u0438\u0448\u044c \u0442\u0435\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c \u0441 \u043e\u0434\u043d\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c, \u0430 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0449\u0435\u0440\u044b \u0441 \u0434\u0432\u0443\u043c\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438. \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0438\u0447\u0435\u043c \u043d\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0433\u043b\u0430\u0432\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u044c \u043d\u0435 \u043f\u0435\u0449\u0435\u0440\u0430 \u0430 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0442\u0438\u043f \u0434\u0430\u043d\u043d\u044b\u0445 \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e MazeWrapper<\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 MazeWrapper?<\/summary>\n<div class=\"spoiler__content\">\n<ul>\n<li>\n<p>MazeWrapper \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0432 \u0441\u0435\u0431\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u0432 \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c \u043a\u0430\u043a \u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c, \u0432\u0441\u0435 \u044d\u0442\u043e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u043f\u0435\u0440\u0435\u0433\u0440\u0443\u0436\u0435\u043d\u043d\u043e\u043c\u0443 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0443 \u043a\u0440\u0443\u0433\u043b\u044b\u0445 \u0441\u043a\u043e\u0431\u043e\u0447\u0435\u043a<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"cpp\">template &lt;> struct BasicWrapper&lt;kMaze> final {   using data_type = std::vector&lt;size_type>;    data_type right, bottom;   size_type rows = 0, cols = 0;    bool IsGood() const {     \/\/ Some checks   }    size_type &amp;operator()(size_type row, size_type col, bool is_right = true) {     return is_right ? right[row * cols + col] : bottom[row * cols + col];   }    size_type operator()(size_type row, size_type col, bool is_right = true) const {     return is_right ? right[row * cols + col] : bottom[row * cols + col];   } };  using MazeWrapper = BasicWrapper&lt;kMaze>;<\/code><\/pre>\n<ul>\n<li>\n<p>\u0418\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e \u0447\u0442\u043e \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0445\u0440\u0430\u043d\u0438\u0442 \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0432 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0435 \u043a\u0440\u0443\u0433\u043b\u044b\u0445 \u0441\u043a\u043e\u0431\u043e\u043a \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d bool \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0432\u043d\u0435 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0432\u044b\u0431\u0438\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<ul>\n<li>\n<p>\u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0434\u043b\u044f \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u043e\u0439 \u0432\u043e\u043b\u043d\u044b \u0438 \u043f\u0440\u0438 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 (\u0432\u0441\u0435 \u044d\u0442\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u0442\u0435\u043c \u043a\u0430\u043a \u044d\u0442\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043c \u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435)<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u043e\u0432\u0430\u044f \u0432\u043e\u043b\u043d\u0430<\/h2>\n<pre><code class=\"cpp\">bool StepWave(const MazeWrapper &amp;maze, Point to) {   ++wave_step;   for (auto [row, col] : old_wave) {     for (auto [x, y, value] : {SidePoint{row + 1, col, maze(row, col, false)},                                SidePoint{row - 1, col, maze(row - 1, col, false)},                                SidePoint{row, col + 1, maze(row, col)},                                SidePoint{row, col - 1, maze(row, col - 1)}}) {       if (value == 0) {         if (length_map(x, y) == -1) {           wave.emplace_back(x, y);           length_map(x, y) = wave_step;         }          if (x == to.x and y == to.y)           return true;       }     }   }<\/code><\/pre>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-349651","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/349651","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=349651"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/349651\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=349651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=349651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=349651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}