Zajak od MOI 2015

This message was edited 1 time. Last update was at 14/03/2019 16:23:06

Zdravo, moze nekoj da mi kaze zosto imam Runtime error?

#include <bits/stdc++.h>

using namespace std;
const int MAX=1000+10;
const int INF=(1<<30);
int n,m;
int mat[MAX][MAX];
bool vis[MAX][MAX];
int carrots[MAX][MAX];
bool valid_move(int i, int j)
{
    if(i+1>=n || vis[i][j])
    {
        return false;
    }
    return true;
}
void dfs(int si, int sj, int ei, int ej)
{
    if(si==n)//Dali mozebi sum do isti red, togas dozvolen e samo skok
    {
        int zbir=carrots[si][sj];
        for(int i=sj; i<m; i++)
        {
            zbir+=carrots[si][i];
        }
        cout<<zbir<<endl;
        return;
    }
    if(si==ei&&sj==ej)//Dali mozebi sum vekje do krajot
    {
        cout<<carrots[si][sj]<<endl;
        return;
    }
    //Dali mozam da napravam cekor
    //Vo prodolzenie baram dali ne izleguvam od matricata ako napravam cekor nadolu
    if(valid_move(si+1,sj))
    {
        carrots[si+1][sj]=max(carrots[si+1][sj],carrots[si][sj]+mat[si+1][sj]);
        vis[si+1][sj]=true;
        dfs(si+1,sj,ei,ej);
        vis[si+1][sj]=false;
    }
    //Gi pominuvam site od ista redica osven poleto na koe shto sum
    for(int i=0; i<m; i++)//imam M koloni
    {
        if(si!=i)
        {
            vis[si][i]=true;
            carrots[si][i]=max(carrots[si][i],carrots[si][sj]+mat[si][i]);
            dfs(si,i,ei,ej);
        }

}
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>mat[i][j];
            vis[i][j]=false;
            carrots[i][j]=0;
        }
    }
    vis[0][0]=true;
    carrots[0][0]=mat[0][0];
    dfs(0,0,n-1,m-1);
    return 0;
}

BATIR wrote:Zdravo, moze nekoj da mi kaze zosto imam Runtime error?

Имаш неколку проблеми кои можеш да ги исправиш, ама конкретно за твоето прашање види ја линија 47 (и дали таму можеби треба да провериш дали vis[si][i] == false за да не заглавиш со рекурзијата).

Aa, pa ne ni primetiv deka nemam staveno za vis. Sega ushte imam greska vo dvizenje vo drug red

#include <bits/stdc++.h>

using namespace std;
const int MAX=1000+10;
const int INF=(1<<30);
int n,m;
int mat[MAX][MAX];
bool vis[MAX][MAX];
int carrots[MAX][MAX];
bool valid_move(int i, int j)
{
    if(i+1<n || !vis[i][j])
    {
        return true;
    }
    return false;
}
void dfs(int si, int sj, int ei, int ej)
{
    if(si==ei)//Dali mozebi sum do isti red, togas dozvolen e samo skok
    {
        int zbir=carrots[si][sj];
        for(int i=sj; i<m; i++)
        {
            zbir+=carrots[si][i];
        }
        cout<<zbir<<endl;
        return;
    }
    if(si==ei&&sj==ej)//Dali mozebi sum vekje do krajot
    {
        cout<<carrots[ei][ej]<<endl;
        return;
    }
    //Dali mozam da napravam cekor
    //Vo prodolzenie baram dali ne izleguvam od matricata ako napravam cekor nadolu
    if(valid_move(si+1,sj))
    {
        carrots[si+1][sj]=max(carrots[si+1][sj],carrots[si][sj]+mat[si+1][sj]);
        vis[si+1][sj]=true;
        dfs(si+1,sj,ei,ej);
        vis[si+1][sj]=false;
    }
    //Gi pominuvam site od ista redica osven poleto na koe shto sum
    for(int i=0; i<m; i++)//imam M koloni
    {
        if(si!=i&&vis[si][i]==false)
        {
            vis[si][i]=true;
            carrots[si][i]=max(carrots[si][i],carrots[si][sj]+mat[si][i]);
            dfs(si,i,ei,ej);
        }

}
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>mat[i][j];
            vis[i][j]=false;
            carrots[i][j]=0;
        }
    }
    vis[0][0]=true;
    carrots[0][0]=mat[0][0];
    dfs(0,0,n-1,m-1);
    /*for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cout<<carrots[i][j]<<" ";
        }
        cout<<endl;
    }*/
    return 0;
}
Vaka pecati povekje vrednosti

Shto mozam da popravam

BATIR wrote:Shto mozam da popravam

Ај ќе пробам малку да ти помогнам, иако баш и не сакам оти треба прво да се потрудиш да си ги најдеш грешките сам/а, преку преземање на тест случаи од МЕНДО, или барем да пишеш подетално за што ти треба помош (а не само една реченица, па да очекуваш некој да троши повеќе време на твојата задача од ти самиот).

Еве ти неколку поправки (со неколку коментари, и доста поедноставен код). Ова решение дава точни одговори.
Размисли сега како можеш да го забрзаш ова решение? Дали мораме секогаш со for циклус да ги вртиме сите броеви во еден ред, или можеби некако однапред да ги откриеме најголемите неколку броеви во тој ред?

#include <bits/stdc++.h>
using namespace std;

const int MAX=1000+10;
const int INF=(1<<30);
int n,m;
int mat[MAX][MAX];
int carrots[MAX][MAX];

void dfs(int si, int sj, int ei, int ej)
{
    if(si==ei&&sj==ej)//Dali mozebi sum vekje do krajot
    {
        return;
    }

if(si==ei)//Dali mozebi sum do isti red, togas dozvolen e samo skok
    {
        int zbir=carrots[si][sj];
        zbir+=mat[ei][ej];

carrots[ei][ej] = max(carrots[ei][ej], zbir);
        return;
    }

//prvo morame skok, pa chekor (ne povekje skokovi, ili povekje chekori naednash)
    for(int i=0; i<m; i++)
    {
        if(sj!=i)
        {
            if (carrots[si][sj]+mat[si][i]+mat[si+1][i] > carrots[si+1][i]) {
                carrots[si+1][i] = carrots[si][sj]+mat[si][i]+mat[si+1][i];
                dfs(si+1, i, ei, ej);
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>mat[i][j];
            carrots[i][j]=0;
        }
    }
    carrots[0][0]=mat[0][0];
    dfs(0,0,n-1,m-1);

cout << carrots[n-1][m-1];
    return 0;
}

Fala mnogu. Sega podrazmisliv za toa shto mi rece, poednostavno. Mozam odnapred da ja znam pozicijata na najgolemiot broj na morkovi vo sekoj red, i ottamu da pravam skok nadolu. Toa bi trebalo da bide tocno, bidejki sekogas go zemame najgolemiot broj na morkovi.