Problem solving techniques (Example problems) (Cont.)

In this post i will show you when to use graphs to solve specific type of problems. To know about graphs and other problem solving techniques you may need to read this.

Problem 14 (Shortest path)

Given a set of cities' paths represented as a two dimensional array grid where grid[i][j] = 1 iff there exists a path between city i to city j. Given two cities src and dst, find the shortest path to go from src to dst. If there is no such path return -1.

Solution // In this problem i will show you how to use BFS to get shortest path

#define N 10 // For the example

int prev[N];
int vis[N];

int find_shortest_path(int paths[][N], int src, int dst) {
    memset(vis, 0, sizeof vis);
    memset(prev, -1, sizeof prev);
   
    queue<int> q;
    q.push(src); // First city
   
    while(!q.empty()) {
        int city = q.front();
        q.pop();

        if(city == dst) break; // We arrived
       
        for(int i = 0; i < N; i++) {
            if(paths[city][i] && !vis[i]) {
                prev[i] = city;
                q.push(i);
                vis[i] = 1;
            }
        }
    }
   
    if(prev[dst] == -1) return -1;
   
    int city = dst, res = 0;
    while(prev[city] != -1) { // Exercise: print the path
        city = prev[city];
        res ++;
    }
 
    return res;
}


Problem 15 (GrafixMask)

SRM 211 DIV-1 Medium

In one mode of the grafix software package, the user blocks off portions of a masking layer using opaque rectangles. The bitmap used as the masking layer is 400 pixels tall and 600 pixels wide. Once the rectangles have been blocked off, the user can perform painting actions through the remaining areas of the masking layer, known as holes. To be precise, each hole is a maximal collection of contiguous pixels that are not covered by any of the opaque rectangles. Two pixels are contiguous if they share an edge, and contiguity is transitive.

You are given a vector<string> named rectangles, the elements of which specify the rectangles that have been blocked off in the masking layer. Each String in rectangles consists of four integers separated by single spaces, with no additional spaces in the string. The first two integers are the window coordinates of the top left pixel in the given rectangle, and the last two integers are the window coordinates of its bottom right pixel. The window coordinates of a pixel are a pair of integers specifying the row number and column number of the pixel, in that order. Rows are numbered from top to bottom, starting with 0 and ending with 399. Columns are numbered from left to right, starting with 0 and ending with 599. Every pixel within and along the border of the rectangle defined by these opposing corners is blocked off.

Return a vector<int> containing the area, in pixels, of every hole in the resulting masking area, sorted from smallest area to greatest.

Solution

#define tall 400
#define width 600

bool Grid[tall][width]; // Represent the graph as a matrix
int nx[] = {0,0,1,-1};  // Sentinels
int ny[] = {-1,1,0,0}; // Sentinels

struct node {            // Graph node
    int x, y;
    node(int x,int y){
        this->x = x;
        this->y = y;
    }
};

int Fill(int x,int y)
{
    stack<node> s; // use DFS
    s.push(node(x,y));

    int result = 0;
    while(!s.empty())
    {
        node top = s.top();
        s.pop();

        if(Grid[top.x][top.y]) continue;

        Grid[top.x][top.y] = true;

        result++;

        for(int f= 0;f<4;f++)
        {
            int newX = top.x+nx[f];
            int newY = top.y+ny[f];
          
            if(!(newX<0 || newX >= tall || newY < 0 || newY >= width || Grid[newX][newY]))  
                     s.push(node(newX, newY));
        }
    }

    return result;
}

class grafixMask
{
public:
    vector <int> sortedAreas(vector <string> rect)
    {
        vector<int> answer;
        stringstream ss;
        int x,y,z,w;
           
        int i;
        for(i = 0;i<rect.size();i++)
        {
            ss << rect[i];
            ss >> x >> y >> z >> w;
           
            for(int j = x;j<=z;j++)
            for(int s= y; s<=w; s++)
                Grid[j][s] = true;
        }
       
        for(i = 0; i<tall; i++)
        for(int j = 0; j<width; j++)
            if(!Grid[i][j])
                answer.push_back(Fill(i,j));

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

        return answer;
    }
};

Problem 16 (Shortest path)

Same as problem 14 but path[i][j] = c, that means path from city i to city j equals c KM. find the shortest path from city src, to city dst. In this problem we won't be able to use BFS. Why?

Dijkstra Solution

#define N 5

int graph[N][N];
bool vis[N];

struct node {
    int indx;
    int cst;
};

bool operator < (const node& n1, const node& n2) {
    return n1.cst > n2.cst;
}

int dijkstra(int src, int dst) {
    priority_queue<node> pq;
    pq.push(node(src, 0));
   
    while(!pq.empty()) {
        node n = pq.top();
        pq.pop();
       
        if(vis[n.indx]) continue;
        else if(n.indx == dst)          
                   return n.cst;

        vis[n.indx] = true;
       
        for(int i = 0; i < N; i++)
            if(graph[n.indx][i] != INT_MAX)
                pq.push(node(i, n.cst+graph[n.indx][i]));
     }
   
    return -1;
}

Floyd Warshall  Solution

int floyd_warshall()
{
    int i, j, k;
   
    for(k = 0; k < N; k++)
    for(i = 0; i < N; i++)
    for(j = 0; j < N; j++)
    if(graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
    graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);

    cout << graph[0][3] << endl;
}

In the next post i will show you examples to Maximum flow and Minimum Cut problems.