Return to Question

The problem is as follows: I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths can there be in such a matrix, starting on the right above the castle and terminating on the right below the castle. I proceed as below: Search for a start field and target field, if none then there is no path. If I find them I start Dijkstra search for the shortest path. If I find a path then mark it as impassable. Then start again searching for start and target field.

The problem I have is with the performance. This is slow for big size matrix. How can I improve that?

The problem is as follows:

I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths can there be in such a matrix, starting on the right above the castle and terminating on the right below the castle.

I proceed as such:

1. I search for a start field and target field, if none then there is no path.
2. If I find them I start Dijkstra search for the shortest path.
3. If I find a path then mark it as impassable.
4. Then start again searching for start and target field.

The problem I have is with the performance as it's slow for a large-size matrix. How can I improve that?

The problem is as follows: I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths can there be in such a matrix, starting on the right above the castle and terminating on the right below the castle.

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

using namespace std;
constexpr int maxVal = 100000;
using pii = std::pair<int,int>;
using ppi = std::pair<pii,int>; 

int Dijkstra(vector<vector<int>> &graph,  int height, int width, pii source, pii target)
{

    vector <int> dist(height*width, maxVal);
    vector <vector<int>> cost(height,(vector<int> (width,1)));  

    priority_queue < ppi, vector<ppi>, compare> priorityQueue;

    dist[source.first * width + source.second]=0;

    priorityQueue.push(ppi(source, dist[source.first * width + source.second]));

    visited[source.first * width + source.second] = true;

    while(!priorityQueue.empty())
    {
        pii current = priorityQueue.top().first;
        priorityQueue.pop();
        for (auto it = dmove.begin(); it != dmove.end(); ++it)
        {
            {
                int y = current.first + it->first;
                int x = current.second + it->second;
                int index = current.first * width + current.second; 

                if (dist[index]+1 < dist[y*width+x])
                {
                    dist[y*width+x]=dist[index]+1;
                    priorityQueue.push(ppi(pii(y,x),dist[y*width+x]));
                }
            }
        }
    }

    
      if(pathfound) return 1;//path found

    return 0;//no path found
}

The problem is as follows: I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths can there be in such a matrix, starting on the right above the castle and terminating on the right below the castle. I proceed as below: Search for a start field and target field, if none then there is no path. If I find them I start Dijkstra search for the shortest path. If I find a path then mark it as impassable. Then start again searching for start and target field.

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

using namespace std;
constexpr int maxVal = 100000;
using pii = std::pair<int,int>;
using ppi = std::pair<pii,int>;


struct compare
{
    int operator()( const ppi& p1, const ppi &p2)
    {
        return p1.second > p2.second;
    }
};

int Dijkstra(vector<vector<int>> &graph,  int height, int width, pii source, pii target)
{

    vector <int> dist(height*width, maxVal);
    vector <pii> prev(width*height);
    vector <vector<int>> cost(height,(vector<int> (width,1)));
    //possible moves from a field
    vector<pii> dmove;
    dmove.push_back(pii(0, -1));
    dmove.push_back(pii(0, +1));
    dmove.push_back(pii(-1, 0));
    dmove.push_back(pii(+1, 0));

    vector<bool> visited(height*width, false);

    priority_queue < ppi, vector<ppi>, compare> priorityQueue;

    dist[source.first * width + source.second]=0;

    priorityQueue.push(ppi(source, dist[source.first * width + source.second]));

    visited[source.first * width + source.second] = true;

    while(!priorityQueue.empty())
    {
        pii current = priorityQueue.top().first;
        priorityQueue.pop();
        //checking possible moves from the current field
        for (vector<pii>::iterator it = dmove.begin(); it != dmove.end(); ++it)
        {
            {
                int y = current.first + it->first;
                int x = current.second + it->second;
                int index = current.first * width + current.second;//indexing from 2d vector to 1d

                //check if field is valid
                if (x >= 0 && x < width && y >= 0 && y < height && graph[y][x] != 1 && dist[index]+1 < dist[y*width+x] && !visited[y*width+x])
                {
                    dist[y*width+x]=dist[index]+1;

                    prev[y*width+x]=pii(current.first, current.second);

                    priorityQueue.push(ppi(pii(y,x),dist[y*width+x]));

                    visited[y*width+x] = true;
                }
            }
        }
    }

    pii traceBack = target;

    //set the path already traversed to impassable
    if(dist[traceBack.first * width + traceBack.second]!= maxVal)
    {
        graph[traceBack.first][traceBack.second]=1;
        do
        {
            traceBack = prev[traceBack.first * width + traceBack.second];
            graph[traceBack.first][traceBack.second]=1;

        }
        while(traceBack!=source);
        return 1;//path found
    }


    return 0;//no path found
}

pii findTarget(vector<vector<int>> field, int height, int width, int loc)
{
     //search for the next free field under the castle at the right of the matrix
    for(int a=loc; a<=height; a++)
    {
        if(field[a][width]!=1)
        {
            return pii(a,width) ;
        }
    }
    return pii(-1,-1);//no target found
}

pii findStart(vector<vector<int>> field, int height, int width, int loc)
{
     //search for the next free field under the castle at the right of the matrix
    for(int a=loc; a>=0; a--)
    {
        if(field[a][width]!=1)
        {
            return pii(a,width);
        }
    }
    return pii(-1,-1);//no source found
}

int main()
{
    int cases;
    int width, height, nrOfObjects;//field size
    int cx, cy, castleWidth, castleHeight;//castle coordinates
    int xi, yi, widthi, heighti;//impassable terrain

    cin>>cases;

    for(int c=1; c<=cases; c++)
    {
        cin>>width>>height>>nrOfObjects;

        vector<vector<int> > field(height,(vector<int> (width,0)));

        cin>>cx>>cy>>castleWidth>>castleHeight;

        for(int a=0; a<castleHeight; a++)
        {
            for(int b=0; b<castleWidth; b++)
            {
                field[cy+a-1][cx+b-1] = 1;
            }
        }

        for(int i = 0; i<nrOfObjects; i++)
        {
            cin>>xi>>yi>>widthi>>heighti;

            for(int a=0; a<heighti; a++)//set the terrain as obstacle
            {
                for(int b=0; b<widthi; b++)
                {
                    field[yi+a-1][xi+b-1] = 1;
                }
            }
        }

        pii start, target;
        int scouts=0, i=0;

        while(true)
        {
            //search for the start and target node in the field
            start = findStart(field, height-1, width-1, cy-1-i);
            target= findTarget(field, height-1, width-1, cy+castleHeight-1+i);
            //if there is no start or target stop the search
            if(!(target.first==-1 || start.first == -1) )
            {
                i++;//so the search for start and target field dont start from the same spot
                scouts += Dijkstra(field, height, width, start, target);
            }
            else break;

        }

        printf("Case #%d: %d\n", c, scouts);

    }
    return 0;
}

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

using namespace std;
constexpr int maxVal = 100000;
using pii = std::pair<int,int>;
using ppi = std::pair<pii,int>; 

int Dijkstra(vector<vector<int>> &graph,  int height, int width, pii source, pii target)
{

    vector <int> dist(height*width, maxVal);
    vector <vector<int>> cost(height,(vector<int> (width,1)));  

    priority_queue < ppi, vector<ppi>, compare> priorityQueue;

    dist[source.first * width + source.second]=0;

    priorityQueue.push(ppi(source, dist[source.first * width + source.second]));

    visited[source.first * width + source.second] = true;

    while(!priorityQueue.empty())
    {
        pii current = priorityQueue.top().first;
        priorityQueue.pop();
        //checking possible moves from the current field
        for (vector<pii>::iterator it = dmove.begin(); it != dmove.end(); ++it)
        {
            {
                int y = current.first + it->first;
                int x = current.second + it->second;
                int index = current.first * width + current.second;//indexing from 2d vector to 1d

                //check if field is valid
                if (x >= 0 && x < width && y >= 0 && y < height && graph[y][x] != 1 && dist[index]+1 < dist[y*width+x])
                {
                    dist[y*width+x]=dist[index]+1;
                    priorityQueue.push(ppi(pii(y,x),dist[y*width+x]));
                }
            }
        }
    }

    
      if(path) return 1;//path found

    return 0;//no path found
}

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

using namespace std;
constexpr int maxVal = 100000;
using pii = std::pair<int,int>;
using ppi = std::pair<pii,int>; 

int Dijkstra(vector<vector<int>> &graph,  int height, int width, pii source, pii target)
{

    vector <int> dist(height*width, maxVal);
    vector <vector<int>> cost(height,(vector<int> (width,1)));  

    priority_queue < ppi, vector<ppi>, compare> priorityQueue;

    dist[source.first * width + source.second]=0;

    priorityQueue.push(ppi(source, dist[source.first * width + source.second]));

    visited[source.first * width + source.second] = true;

    while(!priorityQueue.empty())
    {
        pii current = priorityQueue.top().first;
        priorityQueue.pop();
        for (auto it = dmove.begin(); it != dmove.end(); ++it)
        {
            {
                int y = current.first + it->first;
                int x = current.second + it->second;
                int index = current.first * width + current.second; 

                if (dist[index]+1 < dist[y*width+x])
                {
                    dist[y*width+x]=dist[index]+1;
                    priorityQueue.push(ppi(pii(y,x),dist[y*width+x]));
                }
            }
        }
    }

    
      if(pathfound) return 1;//path found

    return 0;//no path found
}