+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجمع الجزایر «جچحخ» مجموعه‌ای از جزایر هستند که تشکلیل یک مستطیل $n \times m$ می‌دهند به طوری که هر رأس مستطیل نشان‌دهنده‌ی یک جزیره است (در مجموعه $(m+1)\times(n+1)$ جزیره). برای جابه‌جایی بین جزیره‌ها از کشتی استفاده می‌شود اما هر جزیره مانند `(i,j)` به طوری که $(0 \leq i \leq n , 0 \leq j \leq m)$ به صورت مستقیم فقط به جزیره‌های `(i+1,j-1)` و `(i-1, j+1)` و `(i-1, j-1)` و `(i+1, j+1)` (در صورت وجود) می‌تواند برود. در واقع مسیرهای مستقیم بین جزیره‌ها مانند قطرهای خانه‌های واحد مستطیل هستند. برای جلوگیری از تصادف کشتی‌ها ، در هر خانه‌ی واخد از مستطیل، تنها یکی از دو قطر آن مجوز عبور دارند. برای افزایش دسترسی بین جزیره‌ها مجوز عبور بین دو قطر یک خانه قابل جابه‌جایی است.  برنامه‌ای بنویسید که با گرفتن وضعیت اولیه‌ی مجوز مسیرها و دو جزیره‌ی $(i_s, j_s)$ و $(i_t,j_t)$ کمترین تعداد جابه‌جایی مجوز مورد نیاز را برای رسیدن از $(i_s, j_s)$ به $(i_t,j_t)$ پیدا کند. در صورتی که رسیدن از $(i_s, j_s)$ به $(i_t,j_t)$ امکان‌پذیر نباشد، برنامه‌ی شما باید عدد `1-` را به عنوان جواب در نظر بگیرد. # ورودی سطر اول ورودی شامل دو عدد طبیعی `n` و `m` است. در سطر دوم به ترتیب دو عدد صحیح $i_s$ و $j_s$ آمده است که نشان‌دهنده‌ی جزیره‌ی مبدا $(i_s,j_s)$ است. در سطر سوم به ترتیب دو عدد صحیح $i_t$ و $j_t$ آمده است که نشان‌دهنده‌ی جزیره‌ی مقصد $(i_t,j_t)$ است. در هریک از `n` سطر بعد `m` کاراکتر آمده است که نشان‌دهنده‌ی وضعیت اولیه‌ی قطرها هستند. اگر کاراکتر `j`ام از `i`امین سطر برابر با `\` باشد، مسیر بین جزیره‌های $(i,j)$ و $(i+1,j+1)$ مجوز عبور دارد و در صورتی که این کاراکتر برابر با `/` باشد، مسیر بین جزیره‌های $(1+i,j)$ و $(i+1,j)$ مجوز عبور دارد.( دقت کنید که برای نمایش کاراکتر `\` در زبان `++C` باید از `\\` استفاده کنید.) $$1 \leq n,m \leq 2\ 000$$ $$0 \leq i_s, i_t \leq n$$ $$ 0 \leq j_s, j_t \leq m$$ # خروجی در تنها سطر خروجی کمترین تعداد تعویض مجوز برای رسیدن از جزیره‌ مبدا به جزیره مقصد را پیدا کنید. در صورتی که رسیدن از مبدا به مقصد امکان‌پذیر نیست، عدد `-1` را در خروجی چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۰ | ۱۰۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 1 1 0 0 1 1 / ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 1 4 0 0 0 4 //// ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 2 2 1 1 1 2 /\ /\ ``` ## خروجی نمونه ۳ ``` -1 ```