بیابان ماتریسی آتش فشان

Question

سوال سختیه هر کی تونست لطفا کدشو بفرسته.

 

 

توضیح سوال

دانیال در یک بیابان بسیار بزرگ گم شده است. بیابان را می توان یک ماتریس n × n در نظر گرفت به طوری که هر کدام از سلول های ماتریس بخشی از بیابان است. دانیال از هر سلول فقط می تواند بالا یا پایین رود؛ به عبارت دیگر، اگر او در سلولی (i, j)باشد می تواند به سلولی(i + 1, j) و (i, j + 1) برود.
m سلول نیز با آتشفشان پر شده اند و به همین خاطر دانیال نمی تواند وارد آن ها شود.
در ابتدای حرکت دانیال در سلولی قرار دارد و می خواهد به سلول ی برسد. با دانستن این که برای رفتن از یک سلول به سلولی دیگر 1 ثانیه زمان نیاز است، کمترین مقدار زمان برای رسیدن به خانه ی مورد نظر را بیابید.

ورودی

اولین خط ورودی شامل عدد صحیح n (1 ≤ n ≤ 109) و m (1 ≤ m ≤ 105) می باشد. هر m خط بعدی شامل یک جفت عدد صحیح x و y (1 ≤ x, y ≤ n) می باشند که مختصات سلول هایی که آتشفشان ها در آن ها قرار دارند را نشان می دهند.
فرض کنید ماتریس از بالا به پایین از شماره ی 1 تا n شماره گذاری شده و ستون های آن نیز از چپ به راست شماره گذاری شده اند. تضمین می شود که هیچ آتشفشانی در خانه ی (1, 1)نیست و هیچ دو آتشفشانی نمی توانند در یک سلول باشند.

خروجی

مقدار مورد نظر را چاپ کنید و در صورتی که امکان رسیدن به مقصد وجود ندارد -1 چاپ کنید.

ورودی نمونه

4 2
1 3
1 4

خروجی نمونه

6

Comments

کسی نتونست؟

---

BFS بزن‌‌‌‌‌

Answer 1

این الگوریتم اول همه خونه های ماتریس رو صفر میکنه و با یه چیزی شبیه به BFS کار رو جلو میبره

ویرایش: حالا که فکر میکنم میبینم راه های خیلی ساده تری هم وجود داره. مثل روش پویا در حل مسأله ی مسیر (ترکیبیات -> اصل جمع)

#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    int S[n][n];
    for(int i=0; i<n; i++)  //تمیز کردن
        for(int j=0; j<n; j++)
            S[i][j]=0;
    for(int i=0; i<m; i++)
    {
        int x, y;
        cin>>x>>y;
        S[x-1][y-1]=-5;
    }
    S[0][0]=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(S[i][j]!=-5)
            {
                if(S[i][j]+1 < S[i][j+1] || S[i][j+1] == 0)
                    if(S[i][j+1] != -5)
                        S[i][j+1] = S[i][j]+1;
                if(S[i][j]+1 < S[i+1][j] || S[i+1][j] == 0)
                    if(S[i+1][j] != -5)
                        S[i+1][j] = S[i][j]+1;
            }
        }
    }
    if(S[n-1][n-1] == 0)
        cout<<-1<<endl;
    else
        cout<<(S[n-1][n-1])<<endl;
    return 0;
}