Messages posted by: shellcode

Да појаснам малку

1. val може да прима вредност 0 или 1 значи матрицата ја полнам со нули и единици, 0 означува непосетено а 1 посетено поле и затоа користам integer.
2. y користам за редовите, x за колоните. Така ми е полесно. И тука нема никаков проблем.

Проблемот е нешто друго, сеуште незнам што, стварно неможам да видам ниту една друга грешка. Фала на трудот во секој случај. (Ако откриеш кај е проблемот обавезно пиши

).

Здраво. Ако можи некој да го види кодов, никако неможам да најдам што е грешката. Печати некој чуден број кога функцијата враќа вредност (оваа линија: ). Било што да ставам да врати функцијата таа враќа некој голем број. Друго пак, ако на крајот на функцијата ставам или било кој вредност тогаш работи како што треба. If-от секако ќе се изврши затоа што јас ги подесувам крајните координати. Фала

#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int x,y,spath,val;
}v,c;

node mat[100][100];
int dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1}, n, m;

void input()
{
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> mat[i][j].val;
            mat[i][j].spath = 0;
        }
    }
}

int shortest_path(node start, node end)
{
    queue<node> q;
    q.push(start);
    mat[start.y][start.x].val = 1;

while (!q.empty())
    {
        v = q.front();
        q.pop();

for (int i=0; i<4; i++) {
            c.y = v.y + dy[i];
            c.x = v.x + dx[i];

if (c.y == end.y && c.x == end.x) {
                return mat[v.y][v.x].spath + 1;
            }
            else if (c.y >=0 && c.y < n && c.x >=0 && c.x < m && mat[c.y][c.x].val == 0)
                {
                    mat[c.y][c.x].val = 1;
                    mat[c.y][c.x].spath = mat[v.y][v.x].spath + 1;
                    q.push(c);
                }
        }
    }
}

int main()
{
    node start,end;
    start.x = start.y = 0;
    end.y = end.x = 4;
    input();
    cout << shortest_path(start,end) << endl;

for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cout << mat[i][j].spath;
        }
        cout << endl;
    }
    return 0;
}

Фала ви многу, ја решив задачата и конечно ми се разјаснија некои работи. Извинете што вака доцна одговарам

kikoisawsm wrote:Замисли си случај кога точката до која сакаш да стигнеш се наоѓа на координати (5,5). Стигнуваш до точката (4,5) со 1 чекор, па потоа мора да направиш 2 чекори, но неможеш бидејќи сите точки се зафатени. Да стигнеше до точката (4,5) со 3 чекори ќе можеше потоа да направиш 1 чекор за до точката (5,5), но ти веќе си го означил полето за посетено кога си стигнал до него со 1 чекор.

Поради ова не работи моето решение, објаснето ми е ова во првиот пост

Ne ti ja razbiram bas idejata. Ako moze da mi objasnis na konkreten primer bi bilo super. Izvini za latinica od tel sum :p

Здраво. Имам проблем со задачава. Составив решение кое на крајот излезе дека не гарантира точност. Идејата ми беше следнава: Почнувам од "P" и се движам едно поле горе, долу, лево и десно. Тој пат до тоа поле го запишувам во матрица. Потоа се движам од тоа поле до наредните со два чекори горе, долу, лево и десно, после со три чекори исто итн. Ако сретнам некое поле каде што неговата вредност во матрицата( т.е патот да се стигне до тука ) е поголема од таа што ја добивам нова ја запишувам новата. Е сега има случај каде што мојот код вели дека до К нема пат, на пример:

Овде мојот код вели дека нема пат до К, а пат има и е 3. ( Горе за еден, долу два и десно три).
Според моето решение прво се запишува еден во матрицата горе, долу, лево и десно, и кога пробува да оди надолу за 2 гледа дека патот 2 е поголем од 1 што е запишан во полето и завршува.

Еве го кодот:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct coords
{
    int x,y,counter;
};

int matrix_n[300][300];
char matrix_c[300][300];

bool up(coords c, int counter);
bool down(coords c, int counter, int n);
bool left(coords c, int counter);
bool right(coords c, int counter, int m);

int main()
{

int n,m;

cin >> n >> m;

coords end,c,start;

for (int i=0; i<n; i++)
        {
            for (int v=0; v<m; v++)
                {
                    cin >> matrix_c[i][v];
                        if (matrix_c[i][v] == '#')
                            matrix_n[i][v] = -1;
                        else
                            matrix_n[i][v] = 9999;
                        if (matrix_c[i][v] == 'K')
                            {
                                end.y = i;
                                end.x = v;
                                matrix_c[i][v] = '.';
                            }
                        if (matrix_c[i][v] == 'P')
                            {
                                matrix_n[i][v] = 0;
                                matrix_c[i][v] = '.';
                                start.x = v;
                                start.y = i;
                            }
                }
        }

vector <coords> visited;
bool isv = false;
coords temp;

queue<coords> q;

c.y = start.y;
c.x = start.x;
c.counter = 1;

q.push(c);

while(!q.empty()){

isv = false;

c = q.front();
if (c.counter > 3 ) c.counter = 1;
temp = c;

visited.push_back(c);

q.pop();

if (right(c,c.counter,m) == true)
    {
        if (matrix_n[c.y][c.x] + 1 < matrix_n[c.y][c.x + c.counter])
            {
                matrix_n[c.y][c.x + c.counter] = matrix_n[c.y][c.x] + 1;
            }
        c.x = c.x + c.counter;
        c.counter = c.counter + 1;

for (int i=0; i<visited.size(); i++)
            {
                if (visited.at(i).y == c.y && visited.at(i).x == c.x) isv = true;
            }
        if (isv == false) q.push(c);
    }
c = temp;

if ((down(c,c.counter,n) == true))
    {
        if (matrix_n[c.y][c.x] + 1 < matrix_n[c.y + c.counter][c.x])
            {
                matrix_n[c.y + c.counter][c.x] = matrix_n[c.y][c.x] + 1;
            }
        c.y = c.y + c.counter;
        c.counter = c.counter + 1;

for (int i=0; i<visited.size(); i++)
            {
                if (visited.at(i).y == c.y && visited.at(i).x == c.x) isv = true;
            }
        if (isv == false) q.push(c);
    }
c = temp;

if (left(c,c.counter) == true)
    {
        if (matrix_n[c.y][c.x] + 1 < matrix_n[c.y][c.x - c.counter])
            {
                matrix_n[c.y][c.x - c.counter] = matrix_n[c.y][c.x] + 1;
            }
        c.x = c.x - c.counter;
        c.counter = c.counter + 1;

for (int i=0; i<visited.size(); i++)
            {
                if (visited.at(i).y == c.y && visited.at(i).x == c.x) isv = true;
            }
        if (isv == false) q.push(c);
    }
c = temp;

if (up(c,c.counter) == true)
    {
        if (matrix_n[c.y][c.x] + 1 < matrix_n[c.y - c.counter][c.x])
            {
                matrix_n[c.y - c.counter][c.x] = matrix_n[c.y][c.x] + 1;
            }
        c.y = c.y - c.counter;
        c.counter = c.counter + 1;

for (int i=0; i<visited.size(); i++)
            {
                if (visited.at(i).y == c.y && visited.at(i).x == c.x) isv = true;
            }
        if (isv == false) q.push(c);
    }
c = temp;

}

cout << matrix_n[end.y][end.x] << endl;

return 0;
}

bool up(coords c, int counter)
{
    if ((c.y - counter) >= 0)
        {

for (int i=c.y; i>=c.y - counter; i--)
                {
                    if (matrix_c[i][c.x] == '#') return false;
                }

return true;
        }
    return false;
}

bool down(coords c, int counter, int n)
{
    if (c.y + counter < n)
        {
            for (int i=c.y; i<=c.y + counter; i++)
                {
                    if (matrix_c[i][c.x] == '#') return false;
                }
            return true;
        }
    return false;
}

bool left(coords c, int counter)
{
    if (c.x - counter >= 0)
        {
            for (int i=c.x; i>=c.x - counter; i--)
                {
                    if (matrix_c[c.y][i] == '#') return false;
                }
            return true;
        }
    return false;
}

bool right(coords c, int counter, int m)
{
    if (c.x + counter < m)
        {
            for (int i=c.x; i<=c.x + counter; i++)
                {
                    if (matrix_c[c.y][i] == '#') return false;
                }
            return true;
        }
    return false;
}

Друго решение што ми текнува е да почниме од К. На пример ја имаме следната матрица:

До К може да се стигне со еден чекор од полето (1,1) и со два чекори од полето (1,0). Ако пробаме да стигнеме од (1,1) со еден чекор значи до него сме стигнале со три чекори. Гледаме дека до него неможе да се стигне со три чекори така што тој испаѓа од игра. Пробуваме од (1,0). Ако до К стигнеме од (1,0) со два чекори, тогаш до него сме стигнале со еден чекор. Гледаме дека со еден чекор може да се стигне од P и имаме решение. Проблемот во ова е што незнам како да го напишам

Ако може некоја идеја да ми дадете или било каква помош би ви бил благодарен. Поздрав

Се согласувам со погорниот пост. Вака регионалниот не би имал никакво значење, а и би се изгубила смислата за натпревар..

Здраво. Ако може некој хинт за подобрување на решениево

Моево решение на задачава ми поминува само на 4 случаи, а на другите ми дава runtime error затоа што неможам да ја направам матрицата голема колку што треба. Ако може малку помош, идеја за било што да се подобри или како да се пристапи поинаку, буквално секој совет би бил добредојден и би ми користел. Фала однапред

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int matrix[4000 + 1][4000 + 1];

void DFS(int visited[], int v, int n);

int main(){

int n;
cin >> n;

int initial[n + 1];

for (int i=1; i<=n; i++) cin >> initial[i];

int initial_index[n + 1];

for (int i=1; i<=n; i++) initial_index[i] = i;

int visited[n + 1];

for (int i=1; i<=n; i++) visited[i] = 0;

for (int i=1; i<=n; i++)
{
    for (int j=1; j<=n; j++)
        matrix[i][j] = 0;
}

for (int i=1; i<=n; i++)
{
        matrix[initial_index[i]][initial[i]] = 1;
}

vector<int> maximum;
int number = 0;

for (int i=1; i<=n; i++)
{
    number = 0;
    for (int x=1; x<=n; x++) visited[x] = 0;

DFS(visited,i,n);
        for (int j=1; j<=n; j++) if (visited[j] == 1) number++;
        maximum.push_back(number);

}

sort(maximum.begin(),maximum.end());

cout << maximum.at(maximum.size() - 1);

return 0;
}

void DFS(int visited[], int v, int n)
{
    visited[v] = 1;
        for (int i=1; i<=n; i++)
        {
            if (matrix[v][i] == 1 && visited[i] == 0)
                DFS(visited, i, n);
        }
}

Здраво. Дали некој би можел да ми даде идеја како се решава задачава? фала однапред

И од мене едно прашање: Дали поканетите натпреварувачи можат да учествуваат на квалификациониот натпревар иако се постари од 15.5 (имаат на пример 15.6, 15.7 или 15.8 години)

Благодарам

5ката значи колку броеви се внесуваат. Океј си е излезот

нема врска, ја решив

Двосмислено е, секој може да го протолкува различно. Затоа мислам дека треба да се појасни малку во текстот за што станува збор, да нема забуни.

поздрав

Во задачава имате напишано дека цифрите на регистрираните корисници се движат од 0 до 9 а во тест примерите имате и над 9. Поправете да се знае дека има броеви и над 9.

Сепак, целта ни е да се даде најмалиот слободен број за таа варијанта. Забележете дека регистрираните корисничките имиња се состојат од мали латинични букви ('a'-'z') и цифри ('0' до '9'), додека корисничкото име кое што првично го избира корисникот е составено само од мали латинични букви.

Поздрав, се најубаво

Ако може некој да ми го објасни решениево на задачава, не го сфаќам воопшто

? Фала однапред