Messages posted by: BATIR

Fala mnogu☺️

Raboti na 6/20. Ne znam kade pravam greska. Kje mi pomogne nekoj?

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
int n,m;
char mat[51][51];
bool vis[51][51];
vector<pair<int,int> > v1,v2,v3,e;
int di[4]={0,0,-1,1};
int dj[4]={1,-1,0,0};

bool valid_move(int i, int j)
{
    if(i<0 || i>=n || j<0 || j>=m || mat[i][j]=='#')return false; // dali e ok potegot
    return true;
}

bool to_the_end(vector<pi> v)
{

for(int i=0; i<v.size(); i++)
    {
        if(v[i].first==e[i].first && v[i].second==e[i].second)continue; // dali stignav do F-s
        else return false;
    }
    return true;
}
int bfs(vector<pi> start,vector<pi> end)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            vis[i][j]=false;
        }
    }
    queue<vector<pair<int,int> > > q;
    vector<pair<int,int> > v5;
    for(pi curr :start)
    {
        int i=curr.first;
        int j=curr.second;  //mu pravi true na site od pocetniot klavir
        vis[i][j]=true;
        v5.push_back({i,j});
    }
    q.push(v5);
    queue<int> cekor;
    cekor.push(0);
    while(!q.empty())
    {
        vector<pi> v=q.front();
        q.pop();
        int c=cekor.front();
        cekor.pop();
        if(to_the_end(v))return c; // ako stignav do kraj
        for(int k=0; k<4; k++)
        {
            vector<pi> nov;
            bool flag=false;
            for(int z=0; z<v.size(); z++)
            {
                nov.push_back({v[z].first+di[k],v[z].second+dj[k]}); // go pomestuva cel objekt na nekoja nasoka
                if(vis[v[z].first+di[k]][v[z].second+dj[k]]==true)flag=true;
            }
            bool can=true;
            for(int z=0; z<nov.size(); z++)
            {
                if(!valid_move(nov[z].first,nov[z].second)) // proveruva dali validna nasokata
                {
                    can=false;
                    break;
                }
            }
            if(can && !flag)
            {
                q.push(nov);
                cekor.push(c+1);
                for(int i=0; i<nov.size(); i++)
                {
                    vis[nov[i].first][nov[i].second]=true; // ako moze go zemam vektorot
                }
            }
        }
    }
    return -1;

}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {

cin>>mat[i][j];
            if(mat[i][j]=='1')
            {
                v1.push_back({i,j});
            }
            else if(mat[i][j]=='2')
            {
                v2.push_back({i,j});
            }
            else if(mat[i][j]=='3')
            {
                v3.push_back({i,j});
            }
            else if(mat[i][j]=='F')
            {
                e.push_back({i,j});
            }
        }
    }
    vector<int> res;
    res.push_back(bfs(v1,e));
    if(v2.size()>0)res.push_back(bfs(v2,e));
    if(v3.size()>0)res.push_back(bfs(v3,e));
    int ret=1000000;
    int type=1;
    for(int i=0; i<res.size(); i++)
    {
        if(res[i]==0  || res[i]==-1)continue;
        if(res[i]<ret)
        {
            ret=res[i];
            type=i+1;
        }
    }
    if(ret==1000000)cout<<-1<<endl;
    else cout<<type<<endl<<ret<<endl;
    return 0;
}

Spored mene , ovaa zadaa se resava so dp, samo ako nekoj znae moze da mi dae hint kako kje ide dinamickoto...
Fala odnapred

Zdravo, dali nekoj znae kako se resava ovaa zadaca, ja resiv za test slucaevite kade n<1 000 000, no pagja na vreme za drugite bidejki ja probuvam sekoja kombinacija.

Moze ideja kako da go podobram kodov. Pagja na vreme,bidejki na sekoj cekor vo for-ot pravam memset, a nemam podobra ideja.

Vekje ima edna tema na ovaa zadaca, i znam deka otprilika e slicna kako zadacata od drzavniot no sepak razlicna. Ama ovoj pat ja analizirav podobro i pravam pristap so brute-force, vaka nesto. Bidejki pravam while se dodeka ima promeni, a dolzinata na stringot moze da bide do 100000, zatoa toa bi pagjalo na vreme.
Eve go kodot koj pominuva na 7/10 test sluchai, kade shto poslednite tri pagjaat na vreme. Eve go kodot shto go iskucav, kje zamolam nekoj koj ja ima reseno zadacata, ili znae kako se resava, da mi dade idea za nekoj pristap, shto ne e brute-force. Fala odnapred.
http://mendo.mk/Task.do?id=196

Nikade nemav staveno vis[at]=true. Fala mnogu, treba uste da najdam podobar nacin na memset, malku go izmenav, bidejki na sekoe pravam memset vo forot , a toa e mnogu vo odnos na vreme + rekurzijata, shto zema vreme.

Zdravo. Moze nekoj da mi kaze zosto imam runtime error. Probuvam so rekurzija da stignam do nekoe pole kade vekje sum bila i vrakjam kolku lugje sme opfatile. I go baram maksimumot.
http://mendo.mk/Task.do?id=174

Razmisli na nekoj drug nacin za pristap

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.

Shto mozam da popravam

#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

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

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;
}