2.7 years ago

Nilesh Pingale • 0

int main(){

#ifndef ONTLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);
int m, diceroll;
cin>>m>>diceroll;

int n ;

cin>>n;
vector<int>nums;
for(int i = 0 ; i < n ; i++)
{
    int x , y;
    cin>>x>>y;
    nums.push_back(x);
    nums.push_back(y);
}
int s ,e;
cin>>s>>e;;
cout<<solve(m , nums , s , e ,diceroll);

return 0;
}

int solve(int matrixsizes , vector&arr , int start , int end , int diceroll)
{

   matrixsizes = matrixsizes*matrixsizes;
   unordered_map<int , int>mp;
   for(int i = 0 ; i < arr.size() ; i+=2)
   {
       mp[arr[i]] = arr[i+1];
   }
    vector<int>visited(matrixsizes+1 ,0);
    queue<pair<int, int>>q;
    q.push({start , 0});
    while(!q.empty())
    {
        int step = q.front().second;
        int pos = q.front().first;
        q.pop();
        if(pos == end) return step;
        for(int k = 1 ; k<= diceroll ; k++)
        {
            int loc = pos+k;
            if(loc>matrixsizes) break;
            
            if(visited[loc] == 1)continue;
            
            visited[loc] = 1;
            if(mp.find(loc) != mp.end())
            {
                q.push({mp[loc] , step+1});
            }
            else q.push({loc , step+1});
        }
    }
    return -1;
}

2.6 years ago

Eren • 0

int* solve(int matrixsize1, int maxDice1, int numcoordinates_count, int *numcordinates, int startpoint1, int endpoint1) {
    int ans = (int)malloc(sizeof(int) * 3);

    int snakes[matrixsize1 * matrixsize1 + 1];
    int ladders[matrixsize1 * matrixsize1 + 1];
    for (int i = 0; i < numcoordinates_count; i += 2) {
        if (numcordinates[i] > numcordinates[i + 1])
            snakes[numcordinates[i]] = numcordinates[i + 1];
        else
            ladders[numcordinates[i]] = numcordinates[i + 1];
    }

    int vis[matrixsize1 * matrixsize1 + 1];
    for (int i = 0; i <= matrixsize1 * matrixsize1; i++) {
        vis[i] = 0;
    }
    vis[startpoint1] = 1;

    int steps = 0;
    int queue[3][matrixsize1 * matrixsize1 + 1];
    int front = 0, rear = 0;
    queue[0][rear] = startpoint1;
    queue[1][rear] = 0;
    queue[2][rear] = 0;
    rear++;

    while (front != rear) {
        int sz = rear - front;
        for (int i = 0; i < sz; i++) {
            int x = queue[0][front];
            int y = queue[1][front];
            int z = queue[2][front];
            front++;

            if (x == endpoint1) {
                ans[0] = steps;
                ans[1] = y;
                ans[2] = z;
                return ans;
            }

            for (int j = 1; j <= maxDice1; j++) {
                int ps = x + j;
                if (ps <= matrixsize1 * matrixsize1 && vis[ps] == 0) {
                    vis[ps] = 1;
                    if (ladders[ps] != 0 && vis[ladders[ps]] == 0) {
                        ps = ladders[ps];
                        vis[ps] = 1;
                        queue[0][rear] = ps;
                        queue[1][rear] = y + 1;
                        queue[2][rear] = z;
                        rear++;
                    } else if (snakes[ps] != 0 && vis[snakes[ps]] == 0) {
                        ps = snakes[ps];
                        vis[ps] = 1;
                        queue[0][rear] = ps;
                        queue[1][rear] = y;
                        queue[2][rear] = z + 1;
                        rear++;
                    } else {
                        queue[0][rear] = ps;
                        queue[1][rear] = y;
                        queue[2][rear] = z;
                        rear++;
                    }
                }
            }
        }
        steps++;
    }
    result1[0] = 1;
    ans[0] = -1;
    return ans;
}

- NthD