This one took me a looong time to figure out the solution, i used dynamic programming approach to modify the bfs traversal.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <fstream>
#include <string>
#include <map>
#include <queue>
#define INF 100000000
//#define ll long long
#define PASS 2
#define NEED 1
#define NONEED 0
#define HORIZON 1
#define VERTICAL 2
using namespace std;
struct PP{
int x,y;
int rank,Rrank;
int MINIMUM,rMINIMUM;
};
vector<int> noOfwaysWithTurnsXenter[4500];
vector<int> noOfwaysWithTurnsYenter[4500];
vector<int> RnoOfwaysWithTurnsXenter[4500];
vector<int> RnoOfwaysWithTurnsYenter[4500];
int resTurns,resPathCount;
bool visited[4500];
int indexMap[50][90];
PP MapIndex[4500];
string str[50];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int stx=-1,sty=-1,edx=-1,edy=-1;
bool visit[50][90];
int PathLength;
int height=0;
int src,dst;
int nodeCount;
//bool NewLine=0;
//ofstream out;
void init()
{
int k=0;
resTurns=-1;
resPathCount=-1;
PathLength=-1;
for(int i=0;i<50;i++)
{
for(int j=0;j<90;j++)
{
visit[i][j]=0;
indexMap[i][j]=-1;
MapIndex[k].rank=-1;
MapIndex[k].Rrank=-1;
MapIndex[k].MINIMUM=INF;
MapIndex[k].rMINIMUM=INF;
MapIndex[k].x=-1;
MapIndex[k].y=-1;
while(noOfwaysWithTurnsXenter[k].size()!=0)
noOfwaysWithTurnsXenter[k].pop_back();
while(noOfwaysWithTurnsYenter[k].size()!=0)
noOfwaysWithTurnsYenter[k].pop_back();
while(RnoOfwaysWithTurnsXenter[k].size()!=0)
RnoOfwaysWithTurnsXenter[k].pop_back();
while(RnoOfwaysWithTurnsYenter[k].size()!=0)
RnoOfwaysWithTurnsYenter[k].pop_back();
k+=1;
}
}
}
void print()
{
for(int i=0;i<=height;i++)
cout<<str[i]<<"\n";
}
bool visitCount()
{
bool ret=0;
int MX;
queue<int> parentNodes;
while(!parentNodes.empty())
parentNodes.pop();
int m,x,y,tx,ty,trnk;
int n;
int counter=0;
int i;
for(int jj=0;jj<4500;jj++)
visited[jj]=0;
indexMap[stx][sty]=counter;
MapIndex[counter].x = stx;
MapIndex[counter].y = sty;
MapIndex[counter].rank = 0;
visit[stx][sty]=1;
visited[0]=1;
noOfwaysWithTurnsXenter[counter].push_back(0);
noOfwaysWithTurnsYenter[counter].push_back(0);
for(int j=0;j<4;j++)
{
tx = stx+dx[j];
ty = sty+dy[j];
if(tx>=0 && ty>=0 && tx<height && ty<str[tx].size() && str[tx][ty]!='X' && visit[tx][ty]==0)
{
counter+=1;
visit[tx][ty]=1;
indexMap[tx][ty]=counter;
MapIndex[counter].x = tx;
MapIndex[counter].y = ty;
MapIndex[counter].rank = 1;
visited[indexMap[tx][ty]]=1;
parentNodes.push(indexMap[tx][ty]);
if(dx[j]==0)
{
noOfwaysWithTurnsYenter[indexMap[tx][ty]].push_back(1);
noOfwaysWithTurnsXenter[indexMap[tx][ty]].push_back(0);
MapIndex[indexMap[tx][ty]].MINIMUM=0;
}
else if(dy[j]==0)
{
noOfwaysWithTurnsXenter[indexMap[tx][ty]].push_back(1);
noOfwaysWithTurnsYenter[indexMap[tx][ty]].push_back(0);
MapIndex[indexMap[tx][ty]].MINIMUM=0;
}
}
}
while(!parentNodes.empty())
{
i = parentNodes.front();
parentNodes.pop();
x = MapIndex[i].x;
y = MapIndex[i].y;
if(x==edx && y==edy)
{
ret = 1;
break;
}
//find adjacexnt higher ranks and visit count
//if it accessed from x axis modify all parents path count of yaxis of parents each time increasing one turn
for(int j=0;j<4;j++)
{
tx = x+dx[j]; ty = y+dy[j];
if(tx>=0 && ty>=0 && tx<height && ty<str[tx].size() && str[tx][ty]!='X')
{
if(visit[tx][ty]==0)
{
counter+=1;
visit[tx][ty]=1;
indexMap[tx][ty]=counter;
MapIndex[counter].x=tx;
MapIndex[counter].y=ty;
MapIndex[counter].rank=MapIndex[i].rank+1;
for(int ii=0;ii<(MapIndex[counter].rank+5);ii++)
{
noOfwaysWithTurnsXenter[counter].push_back(0);
noOfwaysWithTurnsYenter[counter].push_back(0);
}
visited[indexMap[tx][ty]]=1;
parentNodes.push(indexMap[tx][ty]);
}
if(dx[j]==0 && MapIndex[i].rank+1==MapIndex[indexMap[tx][ty]].rank)
{
for(int jj=0;jj<noOfwaysWithTurnsYenter[i].size();jj++)//=MapIndex[i].rank
{
noOfwaysWithTurnsYenter[indexMap[tx][ty]][jj]=noOfwaysWithTurnsYenter[i][jj]+noOfwaysWithTurnsYenter[indexMap[tx][ty]][jj];
noOfwaysWithTurnsYenter[indexMap[tx][ty]][jj+1]=noOfwaysWithTurnsXenter[i][jj]+noOfwaysWithTurnsYenter[indexMap[tx][ty]][jj+1];
}
}
else if(dy[j]==0 && MapIndex[i].rank+1==MapIndex[indexMap[tx][ty]].rank)
{
for(int jj=0;jj<noOfwaysWithTurnsXenter[i].size();jj++)//=MapIndex[i].rank
{
noOfwaysWithTurnsXenter[indexMap[tx][ty]][jj]=noOfwaysWithTurnsXenter[i][jj]+noOfwaysWithTurnsXenter[indexMap[tx][ty]][jj];
noOfwaysWithTurnsXenter[indexMap[tx][ty]][jj+1]=noOfwaysWithTurnsYenter[i][jj]+noOfwaysWithTurnsXenter[indexMap[tx][ty]][jj+1];
}
}
}
}//for ends
}
nodeCount = counter+1;
return ret;
}
void visitCount2()
{
int x,y,tx,ty,trnk;
int MX;
queue<int> parentNodes;
while(!parentNodes.empty())
parentNodes.pop();
int parent=indexMap[edx][edy];
MapIndex[parent].Rrank=0;
int i;
int rnk = MapIndex[parent].Rrank;//PathLength-1;
for(int jj=0;jj<4500;jj++)
visited[jj]=0;
visited[indexMap[edx][edy]]=1;
for(int j=0;j<4;j++)
{
tx = edx+dx[j];
ty = edy+dy[j];
if(tx>=0 && ty>=0 && tx<height && ty<str[tx].size() && str[tx][ty]!='X' && indexMap[tx][ty]!=-1)//&& MapIndex[indexMap[tx][ty]].rank==MapIndex[parent].rank-1
{
MapIndex[indexMap[tx][ty]].Rrank=1;
visited[indexMap[tx][ty]]=1;
parentNodes.push(indexMap[tx][ty]);
if(dx[j]==0)
{
RnoOfwaysWithTurnsYenter[indexMap[tx][ty]].push_back(1);
RnoOfwaysWithTurnsXenter[indexMap[tx][ty]].push_back(0);
MapIndex[indexMap[tx][ty]].rMINIMUM=0;
}
else if(dy[j]==0)
{
RnoOfwaysWithTurnsXenter[indexMap[tx][ty]].push_back(1);
RnoOfwaysWithTurnsYenter[indexMap[tx][ty]].push_back(0);
MapIndex[indexMap[tx][ty]].rMINIMUM=0;//vertical move x changes
}
}
}
while(!parentNodes.empty())
{
i = parentNodes.front();
parentNodes.pop();
x = MapIndex[i].x;
y = MapIndex[i].y;
rnk = MapIndex[i].Rrank;
if(x==stx && y==sty)
break;
for(int j=0;j<4;j++)
{
tx = x+dx[j]; ty = y+dy[j];
if(tx>=0 && ty>=0 && tx<height && ty<str[tx].size() && str[tx][ty]!='X' && indexMap[tx][ty]!=-1)
{
if(visited[indexMap[tx][ty]]==0)
{
visited[indexMap[tx][ty]]=1;
parentNodes.push(indexMap[tx][ty]);
MapIndex[indexMap[tx][ty]].Rrank=rnk+1;
for(int ii=0;ii<(MapIndex[indexMap[tx][ty]].Rrank+5);ii++)
{
RnoOfwaysWithTurnsXenter[indexMap[tx][ty]].push_back(0);
RnoOfwaysWithTurnsYenter[indexMap[tx][ty]].push_back(0);
}
}
if(dx[j]==0 && MapIndex[i].Rrank+1==MapIndex[indexMap[tx][ty]].Rrank)
{
for(int jj=0;jj<RnoOfwaysWithTurnsXenter[i].size();jj++)//=MapIndex[i].Rrank
{
RnoOfwaysWithTurnsYenter[indexMap[tx][ty]][jj+1]+=RnoOfwaysWithTurnsXenter[i][jj];
RnoOfwaysWithTurnsYenter[indexMap[tx][ty]][jj]+=RnoOfwaysWithTurnsYenter[i][jj];
}
}
else if(dy[j]==0 && MapIndex[i].Rrank+1==MapIndex[indexMap[tx][ty]].Rrank)
{
for(int jj=0;jj<RnoOfwaysWithTurnsYenter[i].size();jj++)//=MapIndex[i].Rrank
{
RnoOfwaysWithTurnsXenter[indexMap[tx][ty]][jj+1]+=RnoOfwaysWithTurnsYenter[i][jj];
RnoOfwaysWithTurnsXenter[indexMap[tx][ty]][jj]+=RnoOfwaysWithTurnsXenter[i][jj];
}
}
}
}//for ends
}
}
void minfinder()
{
for(int i=0;i<nodeCount;i++)
{
for(int j=0;j<RnoOfwaysWithTurnsXenter[i].size();j++)
{
if(RnoOfwaysWithTurnsXenter[i][j]+RnoOfwaysWithTurnsYenter[i][j]>0)
{
MapIndex[i].rMINIMUM=j;
break;
}
}
for(int j=0;j<noOfwaysWithTurnsXenter[i].size();j++)
{
if(noOfwaysWithTurnsXenter[i][j]+noOfwaysWithTurnsYenter[i][j]>0)
{
MapIndex[i].MINIMUM=j;
break;
}
}
}
}
void func()
{
minfinder();
int pass,x,y;
int temp_rank;
PathLength=0;
resTurns=0;
resPathCount=0;
int index = indexMap[edx][edy];
PathLength = MapIndex[index].rank;
resTurns = MapIndex[index].MINIMUM;
if(resTurns!=INF)
{
resPathCount=noOfwaysWithTurnsXenter[index][resTurns]+noOfwaysWithTurnsYenter[index][resTurns];
cout<<resPathCount<<" paths, "<<PathLength+1<<" points, "<<resTurns<<" turns\n";
}
for(int i=1;i<indexMap[edx][edy];i++)
{
int cary=0;
//check for is there a new turn at the point i or not.
//cross zero-cross non-zero case
if(MapIndex[i].MINIMUM==INF || MapIndex[i].rMINIMUM==INF)
continue;
if(noOfwaysWithTurnsXenter[i][MapIndex[i].MINIMUM]==0 && RnoOfwaysWithTurnsYenter[i][MapIndex[i].rMINIMUM]==0)
{
if(noOfwaysWithTurnsYenter[i][MapIndex[i].MINIMUM]!=0 && RnoOfwaysWithTurnsXenter[i][MapIndex[i].rMINIMUM]!=0)
{
cary=1;
}
}
else if(noOfwaysWithTurnsYenter[i][MapIndex[i].MINIMUM]==0 && RnoOfwaysWithTurnsXenter[i][MapIndex[i].rMINIMUM]==0)
{
if(noOfwaysWithTurnsXenter[i][MapIndex[i].MINIMUM]!=0 && RnoOfwaysWithTurnsYenter[i][MapIndex[i].rMINIMUM]!=0)
{
cary=1;
}
}
if(MapIndex[i].rank+MapIndex[i].Rrank==PathLength && MapIndex[i].MINIMUM+MapIndex[i].rMINIMUM+cary==resTurns)
str[MapIndex[i].x][MapIndex[i].y]='#';
}
print();
}
int main()
{
int x,y,px,py,s,t;
int cnt = 0;
int k=0;
bool ret;
height=0;
//out.open("out_my.txt");
init();
while(getline(cin,str[height]))
{
if(str[height][0]=='_')
{
ret=visitCount();
if(ret==0)
{
cout<<"0 paths, 0 points, 0 turns\n";
print();
}
else
{
visitCount2();
func();
}
height=0;
cnt = 0;
stx=-1;sty=-1;edx=-1;edy=-1;
init();
continue;
}
for(int i=0;i<str[height].size();i++)
{
if(str[height][i]=='@')
{
if(stx==-1)
{
stx = height;
sty = i;
}
else
{
edx = height;
edy = i;
}
}
}
height+=1;
}
//out.close();
return 0;
}