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:
- I 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 as it's slow for a large-size matrix. How can I improve that?
#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;
}
Dijkstras's algorithm
. \$\endgroup\$O(N^3)
time andO(N^2)
additional memory.~N^2
Dijkstras isO(N^4)
time complexity. \$\endgroup\$