Problem 3: (5 2 points) In a city, there are n streets going from east to west a

Question

Problem 3: (5 2 points) In a city, there are n streets going from east to west and numbered from south to north (so, the first street is the southmost one). There are also m avenues going from south to north and numbered from east to west (so, the first avenue is the eastmost one). Design an algorithm that takes a list of dangerous crosses and computes the number of paths going always west or north from the corner of the first street and the first avenue to the corner of the n-th street and the m-th avenue such that the path does not go through dangerous crosses. The complexity of the algorithm should be O(mn).

Explanation / Answer

Here is a sample pseudo code.

crossList: m*n matrix whre 1 indiacate dangerous crossing, 0 indicates safe crossing
pathCount is also m*n matrix used to store number of routes possible from each crossing. all elements must be initialized to -1 indicating not visited
0 indicates no path is possible from that crossing

    int countRoutes(int totalAvaenues, int totalStreets, int[][] crossList, int startAvenue, int startStreet, int[][] pathsCount){
        if (pathsCount[startAvenue][startStreet] > -1)
            return pathsCount[startAvenue][startStreet];
        int count;
        if (startAvenue == totalAvaenues-1 && startStreet == totalStreets-1) //reached destination
            count = 1;
        else if (startAvenue >= totalAvaenues || startStreet >= totalStreets) //in valid path
            count = 0;
        else if (crossList[startAvenue][startStreet] != 0 ) //either it is a dangerous crossing or already visited
            count = 0;
        else
            count = countRoutes(totalAvaenues, totalStreets, crossList, startAvenue + 1, startStreet, pathsCount) +
                countRoutes(totalAvaenues, totalStreets, crossList, startAvenue, startStreet + 1, pathsCount);
        pathsCount[startAvenue][startStreet] = count;
        return count;
    }

this is the recursive approacch. let me know if you have any doubt?

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.