Avoid The Snails

Computer Science Level 5

After the rain, Chris can finally walk back to his hostel. In order to do so, he must go through a park which can be seen as a matrix of size $N\times M$ . The entrance is on the bottom left and the exit is on the top right corner of the park. Chris wants to take the shortest path, so he will only move upward or to the right.

Unfortunately, the snails decided to come out for some fresh air! Each unit square has some number of snails on it. What is the minimum number of snails Chris will need to pass through?

Input File

Details and Assumptions:

The first line consists of two integers $N$ and $M$ , denoting the number of rows and columns, respectively.
The next $N$ lines contain $M$ space separated integers. each number representing the number of snails in that square.
$N = M = 1000$ .
The number of snails in each square is at most 100.

Sample Input

Sample Output

Explanation

Chris walks to the squares that has $1\rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 2$ number of snails respectively.

Inspired by the number of snails I saw on my way back.

The answer is 51841.

2 solutions

Arjen Vreugdenhil
Aug 27, 2016

(Java) I opened the input file in the BufferedReader ipf . Then:

String[] dimensions = ipf.readLine().split(" ");

int N = Integer.parseInt(dimensions[0]);
int M = Integer.parseInt(dimensions[1]);            

String[] values;
int accu[] = new int[M];

for (int y = 0; y < N; y++) {
    values = ipf.readLine().split(" ");
    for (int x = M-1; x >= 0; x--) {
        int snail = Integer.parseInt(values[x]);

        if (y == 0) {
            if (x == M-1) accu[x] = snail;
            else accu[x] = accu[x+1] + snail;
        }
        else if (x == M-1) accu[x] += snail;
        else accu[x] = Integer.min(accu[x],accu[x+1]) + snail;
    }                
}

System.out.println(accu[0]);

The table accu[x] keeps track of the least number of snails from position $x$ in the current row to the exit at the top-right. The main decision making happens using the minimum function: accu[x] represents the number of snails encountered after moving upward, and accu[x+1] the number of snails encountered after moving to the right.

Output:

Resha Dwika Hefni Al-Fahsi
Jan 19, 2017

Using Dijkstra's Algorithm this problem can be solved easily. Here the C++ implementation:

#include<bits/stdc++.h>

#define inf 9999999
typedef std::pair<int,int> ii;
typedef std::pair<int,ii> i_ii;

std::priority_queue< i_ii,std::vector<i_ii>,std::greater<i_ii> > pq;
int v[1001][1001];
int dx[]={-1,0};
int dy[]={0,1};
int dist[1001][1001];

int main(int argc,char *argv[]){

int n,m;

std::cin>>n>>m;

for(int x=0;x<n;x++)
    for(int y=0;y<m;y++){

        std::cin>>v[x][y];
        dist[x][y]=inf;

    }   

    ii source; source.first=n-1; source.second=0;
    ii goal; goal.first=0; goal.second=m-1;

    dist[source.first][source.second]=v[source.first][source.second];

    pq.push(std::make_pair(v[source.first][source.second],source));


    while(!pq.empty()){
        i_ii now=pq.top(); pq.pop();
        int vnow=now.first; ii xy=now.second;

        if(vnow>dist[xy.first][xy.second]) continue;

        for(int i=0;i<2;i++){

            if((xy.first+dx[i]<n) && (xy.first+dx[i]>=0) && (xy.second+dy[i]<m) && (xy.second+dy[i]>=0) && 
                (vnow+v[xy.first+dx[i]][xy.second+dy[i]]<dist[xy.first+dx[i]][xy.second+dy[i]])){

            dist[xy.first+dx[i]][xy.second+dy[i]]=vnow+v[xy.first+dx[i]][xy.second+dy[i]];

            pq.push(std::make_pair(dist[xy.first+dx[i]][xy.second+dy[i]],ii(xy.first+dx[i],xy.second+dy[i])));

            }
        }   
    }   


    std::cout<<dist[goal.first][goal.second]<<std::endl;

}

My output terminal says: "51841"

Avoid The Snails

The answer is 51841.

2 solutions

0 pending reports