Graph Algorithm – Live with passion

Tree construction from Inorder & Preorder [ Microsoft ]

Asif NaeemJuly 27, 2017

Problem: Provided Inorder and PreOrder of a tree. Construct the tree and print it in PostOrder traversal.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include<stdlib.h>
#include <string>

using namespace std;

int preOrderIdx=0;

struct Node{
	int data;
	Node *left;
	Node *rit;
};


int search(int in[],int in_stIndex,int in_endIndex,int data)
{
	for(int i=in_stIndex;i<=in_endIndex;i++)
	{
		if(in[i]==data)
		return i;
	}
}

Node* buildTree(int in[],int pre[],int in_stIndex,int in_endIndex)
{
	//static int preOrderIdx=0;
	if(in_stIndex>in_endIndex)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=pre[preOrderIdx++];
	tNode->left=NULL;
	tNode->rit=NULL;
	if(in_stIndex==in_endIndex)
	return tNode;
	int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data);
	
	tNode->left=buildTree(in,pre,in_stIndex,rootIndex-1);
	tNode->rit=buildTree(in,pre,rootIndex+1,in_endIndex);
	return tNode;
}

void pintPostOrder(Node* res)
{
	Node *tmp;
	if(res!=NULL)
	{
		if(res->left)
		pintPostOrder(res->left);
		if(res->rit)
		pintPostOrder(res->rit);
		cout<<res->data<<" ";
	}
}
int main()
{
	int in[105];
	int pre[105];
	int t,n;
	scanf("%d",&t);
	Node *res,*tmp;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%d",&in[i]);
		for(int i=0;i<n;i++)
			scanf("%d",&pre[i]);
		res=buildTree(in,pre,0,n-1);
		pintPostOrder(res);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

#include <stdio.h>

#include <iostream>

#include <string.h>

#include<stdlib.h>

#include <string>

using namespace std;

int preOrderIdx=0;

struct Node{

int data;

Node *left;

Node *rit;

};

int search(int in[],int in_stIndex,int in_endIndex,int data)

{

for(int i=in_stIndex;i<=in_endIndex;i++)

{

if(in[i]==data)

return i;

}

Node* buildTree(int in[],int pre[],int in_stIndex,int in_endIndex)

{

//static int preOrderIdx=0;

if(in_stIndex>in_endIndex)

return NULL;

Node *tNode = new Node();

tNode->data=pre[preOrderIdx++];

tNode->left=NULL;

tNode->rit=NULL;

if(in_stIndex==in_endIndex)

return tNode;

int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data);

tNode->left=buildTree(in,pre,in_stIndex,rootIndex-1);

tNode->rit=buildTree(in,pre,rootIndex+1,in_endIndex);

return tNode;

}

void pintPostOrder(Node* res)

{

Node *tmp;

if(res!=NULL)

{

if(res->left)

pintPostOrder(res->left);

if(res->rit)

pintPostOrder(res->rit);

cout<<res->data<<" ";

}

int main()

{

int in[105];

int pre[105];

int t,n;

scanf("%d",&t);

Node *res,*tmp;

while(t--)

{

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%d",&in[i]);

for(int i=0;i<n;i++)

scanf("%d",&pre[i]);

res=buildTree(in,pre,0,n-1);

pintPostOrder(res);

}

return 0;

}

The problem was provided as a functional problem in Microsoft interview as here [Courtesy : geeksforgeeks] Solution:

/*
Please note that it's Function problem i.e.
you need to write your solution in the form Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/


/*Complete the code here.
Node is as follows:
struct Node
{
  int data;
  Node* left;
  Node* right;
};
*/

int search(int in[],int in_stIndex,int in_endIndex,int data)
{
	for(int i=in_stIndex;i<=in_endIndex;i++)
	{
		if(in[i]==data)
		return i;
	}
}

Node* newbuildTree(int in[],int pre[], int inStrt, int inEnd,int *preOrderIdx)
{
	if(inStrt>inEnd)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=pre[(*preOrderIdx)++];
	tNode->left=NULL;
	tNode->right=NULL;
	if(inStrt==inEnd)
	return tNode;
	int rootIndex = search(in,inStrt,inEnd,tNode->data);
	
	tNode->left=newbuildTree(in,pre,inStrt,rootIndex-1,preOrderIdx);
	tNode->right=newbuildTree(in,pre,rootIndex+1,inEnd,preOrderIdx);
	return tNode;
}
Node* buildTree(int in[],int pre[], int inStrt, int inEnd)
{
//add code here.
    int preOrderIdx=0;
    newbuildTree(in,pre, inStrt,inEnd,&preOrderIdx);
}

Please note that it's Function problem i.e.

you need to write your solution in the form Function(s) only.

Driver Code to call/invoke your function would be added by GfG's Online Judge.*/

/*Complete the code here.

Node is as follows:

struct Node

{

int data;

Node* left;

Node* right;

};

int search(int in[],int in_stIndex,int in_endIndex,int data)

{

for(int i=in_stIndex;i<=in_endIndex;i++)

{

if(in[i]==data)

return i;

}

Node* newbuildTree(int in[],int pre[], int inStrt, int inEnd,int *preOrderIdx)

{

if(inStrt>inEnd)

return NULL;

Node *tNode = new Node();

tNode->data=pre[(*preOrderIdx)++];

tNode->left=NULL;

tNode->right=NULL;

if(inStrt==inEnd)

return tNode;

int rootIndex = search(in,inStrt,inEnd,tNode->data);

tNode->left=newbuildTree(in,pre,inStrt,rootIndex-1,preOrderIdx);

tNode->right=newbuildTree(in,pre,rootIndex+1,inEnd,preOrderIdx);

return tNode;

}

Node* buildTree(int in[],int pre[], int inStrt, int inEnd)

{

//add code here.

int preOrderIdx=0;

newbuildTree(in,pre, inStrt,inEnd,&preOrderIdx);

}

10986

Asif NaeemMarch 19, 2016

Single source shortest path algorithm and priority_queue used to solve the problem.

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

#define INF 1000000000
#define ll long long

using namespace std;
/*
struct node{
	int dest,weight;
};
*/
int n,m,src,dst;
vector<pair<int,int> > vb[20005];

void dijkstra(vector<ll> distance)
{
	int t_dist,t_node;
	int latency,v;
	pair<int,int> _intPair;
	priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > cue;
	cue.push(pair<int,int> (0,src));
	pair<int,int> tmp;
	while(!cue.empty())
	{
		tmp=cue.top();
		cue.pop();
		t_dist = tmp.first;
		t_node = tmp.second;

		if(t_dist==distance[t_node])//visited or discovered
		{
			for(int i=0;i<vb[t_node].size();i++)
			{
				_intPair = vb[t_node][i];
				v = _intPair.first;
				latency = _intPair.second;
				if(t_dist+latency<distance[v])
				{
					distance[v]=t_dist+latency;
					cue.push(make_pair(distance[v],v));
				}
			}
		}
	}

	if(distance[dst]!=INF)
		printf("%lld\n",distance[dst]);
	else
		printf("unreachable\n");
}

int main()
{
	int t;
	int kase=1;
	int s,d,wt;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d",&n,&m,&src,&dst);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&s,&d,&wt);
			vb[s].push_back(make_pair(d,wt));
			vb[d].push_back(make_pair(s,wt));
		}
		vector<ll> distance(n,INF);
		distance[src]=0;
		printf("Case #%d: ",kase++);
		dijkstra(distance);
		for(int i=0;i<n;i++)
		vb[i].clear();
	}
	return 0;
}

#include <iostream>

#include <queue>

#include <cstdio>

#include <vector>

#define INF 1000000000

#define ll long long

using namespace std;

struct node{

int dest,weight;

};

int n,m,src,dst;

vector<pair<int,int> > vb[20005];

void dijkstra(vector<ll> distance)

{

int t_dist,t_node;

int latency,v;

pair<int,int> _intPair;

priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > cue;

cue.push(pair<int,int> (0,src));

pair<int,int> tmp;

while(!cue.empty())

{

tmp=cue.top();

cue.pop();

t_dist = tmp.first;

t_node = tmp.second;

if(t_dist==distance[t_node])//visited or discovered

{

for(int i=0;i<vb[t_node].size();i++)

{

_intPair = vb[t_node][i];

v = _intPair.first;

latency = _intPair.second;

if(t_dist+latency<distance[v])

{

distance[v]=t_dist+latency;

cue.push(make_pair(distance[v],v));

}

if(distance[dst]!=INF)

printf("%lld\n",distance[dst]);

else

printf("unreachable\n");

}

int main()

{

int t;

int kase=1;

int s,d,wt;

scanf("%d",&t);

while(t--)

{

scanf("%d%d%d%d",&n,&m,&src,&dst);

for(int i=0;i<m;i++)

{

scanf("%d%d%d",&s,&d,&wt);

vb[s].push_back(make_pair(d,wt));

vb[d].push_back(make_pair(s,wt));

}

vector<ll> distance(n,INF);

distance[src]=0;

printf("Case #%d: ",kase++);

dijkstra(distance);

for(int i=0;i<n;i++)

vb[i].clear();

}

return 0;

}

10336

Asif NaeemNovember 28, 2015

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <fstream>
#include <string>
#include <algorithm>

#define INF 1000000000
#define ll long long

using namespace std;

int h,w;
string arr[1010];
bool visit[1010][1010];
int stateCount[26];

struct stateInfo{
	int count;
	int name;
};

vector<stateInfo> vb;

bool cmp(stateInfo a,stateInfo b)
{
	if(a.count!=b.count)
	return a.count>b.count;
	else
	return a.name<b.name;
}
void findSet(int a,int b)
{
	char c = arr[a][b];
	int x,y;
	queue<int> cue;
	cue.push(a);
	cue.push(b);
	visit[a][b]=1;
	while(!cue.empty())
	{
		x = cue.front();cue.pop();
		y = cue.front();cue.pop();
		if(x+1<h && arr[x+1][y]==c && visit[x+1][y]==0)
		{
			visit[x+1][y]=1;
			cue.push(x+1);
			cue.push(y);
		}
		if(x-1>=0 && arr[x-1][y]==c && visit[x-1][y]==0)
		{
			visit[x-1][y]=1;
			cue.push(x-1);
			cue.push(y);
		}
		if(y+1<w && arr[x][y+1]==c && visit[x][y+1]==0)
		{
			visit[x][y+1]=1;
			cue.push(x);
			cue.push(y+1);
		}
		if(y-1>=0 && arr[x][y-1]==c && visit[x][y-1]==0)
		{
			visit[x][y-1]=1;
			cue.push(x);
			cue.push(y-1);
		}
	}
}
int main()
{
	int t,kase=1;
	scanf("%d",&t);
	stateInfo tmp;
	getchar();
	while(t--)
	{
		cin>>h;
		getchar();
		cin>>w;
		getchar();
		vb.clear();
		memset(visit,0,sizeof(visit));
		memset(stateCount,0,sizeof(stateCount));
		for(int i=0;i<h;i++)
		{
			getline(cin,arr[i]);
		}
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(visit[i][j]==0)
				{
					findSet(i,j);
					stateCount[arr[i][j]-'a']+=1;
				}
			}
		}
		cout<<"World #"<<kase++<<"\n";
		for(int i=0;i<26;i++)
		{
			if(stateCount[i]!=0)
			{
				//cout<<char('a'+i)<<": "<<stateCount[i]<<"\n";
				tmp.name = i;
				tmp.count = stateCount[i];
				vb.push_back(tmp);
			}
		}
		sort(vb.begin(),vb.end(),cmp);
		for(int i=0;i<vb.size();i++)
		{
			cout<<char(vb[i].name+'a')<<": "<<vb[i].count<<"\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <iostream>

#include <cstdio>

#include <vector>

#include <stack>

#include <queue>

#include <cmath>

#include <cstring>

#include <fstream>

#include <string>

#include <algorithm>

#define INF 1000000000

#define ll long long

using namespace std;

int h,w;

string arr[1010];

bool visit[1010][1010];

int stateCount[26];

struct stateInfo{

int count;

int name;

};

vector<stateInfo> vb;

bool cmp(stateInfo a,stateInfo b)

{

if(a.count!=b.count)

return a.count>b.count;

else

return a.name<b.name;

}

void findSet(int a,int b)

{

char c = arr[a][b];

int x,y;

queue<int> cue;

cue.push(a);

cue.push(b);

visit[a][b]=1;

while(!cue.empty())

{

x = cue.front();cue.pop();

y = cue.front();cue.pop();

if(x+1<h && arr[x+1][y]==c && visit[x+1][y]==0)

{

visit[x+1][y]=1;

cue.push(x+1);

cue.push(y);

}

if(x-1>=0 && arr[x-1][y]==c && visit[x-1][y]==0)

{

visit[x-1][y]=1;

cue.push(x-1);

cue.push(y);

}

if(y+1<w && arr[x][y+1]==c && visit[x][y+1]==0)

{

visit[x][y+1]=1;

cue.push(x);

cue.push(y+1);

}

if(y-1>=0 && arr[x][y-1]==c && visit[x][y-1]==0)

{

visit[x][y-1]=1;

cue.push(x);

cue.push(y-1);

}

int main()

{

int t,kase=1;

scanf("%d",&t);

stateInfo tmp;

getchar();

while(t--)

{

cin>>h;

getchar();

cin>>w;

getchar();

vb.clear();

memset(visit,0,sizeof(visit));

memset(stateCount,0,sizeof(stateCount));

for(int i=0;i<h;i++)

{

getline(cin,arr[i]);

}

for(int i=0;i<h;i++)

{

for(int j=0;j<w;j++)

{

if(visit[i][j]==0)

{

findSet(i,j);

stateCount[arr[i][j]-'a']+=1;

}

cout<<"World #"<<kase++<<"\n";

for(int i=0;i<26;i++)

{

if(stateCount[i]!=0)

{

//cout<<char('a'+i)<<": "<<stateCount[i]<<"\n";

tmp.name = i;

tmp.count = stateCount[i];

vb.push_back(tmp);

}

sort(vb.begin(),vb.end(),cmp);

for(int i=0;i<vb.size();i++)

{

cout<<char(vb[i].name+'a')<<": "<<vb[i].count<<"\n";

}

return 0;

}

112

Asif NaeemNovember 21, 2015

Tree Summing.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

int I;
string str;
int next_index;
bool PATHFOUND;
bool isEmpty(int a,int b)
{
	if(a+1==b && str[a]=='(' && str[b]==')')
	return 1;
	return 0;
}

int findnum(int idx)
{
	int numfoundAt=-1;
	int num=0;
	bool negative=false;
	for(int i=idx;i<str.size();i++)
	{
		if(str[i]!='(' && str[i]!=')')
		{
			numfoundAt = i;
			if(str[i]=='-')
				negative = 1,
				numfoundAt+=1;
			break;
		}
	}
	while( numfoundAt<str.size() && (str[numfoundAt]-'0')>=0 && (str[numfoundAt]-'0')<=9)
	{
		num*=10;
		num+=(str[numfoundAt]-'0');
		numfoundAt+=1;
	}
	if(negative)
	num*=(-1);
	next_index = numfoundAt;
	return num;
}
//(5 (4 (11 (7()()) (2()()) )  () )
void calc(int a,int b,int sum)
{
	int number = findnum(a);
	int j=next_index;
	int start1,start2,finish1,finish2;
	int left=0,right=0;
	while(j<str.size() && str[j]!='(')
		j+=1;
	left=1;
	start1=j;
	j+=1;
	while(left!=right)
	{
		if(str[j]=='(')
		left+=1;
		if(str[j]==')')
		right+=1;
		j+=1;
	}
	finish1=j-1;

	left=1;right=0;
	start2=j;
	j+=1;
	while(left!=right)
	{
		if(str[j]=='(')
		left+=1;
		if(str[j]==')')
		right+=1;
		j+=1;
	}
	finish2=j-1;
	bool f1 = isEmpty(start1,finish1);
	bool f2 = isEmpty(start2,finish2);
	if(f1==1 && f2==1)
	{
		if(sum+number==I)
		{
			PATHFOUND=1;
			return;
		}
	}
	else if(f1)
	{
		calc(start2,finish2,sum+number);
	}
	else if(f2)
	{
		calc(start1,finish1,sum+number);
	}
	else
	{
		calc(start1,finish1,sum+number);
		calc(start2,finish2,sum+number);
	}
}
//22 (5(4(11(7()())(2()()))())   (8(13()())(4()(1()()))))
int main()
{
	char ch;
	int j,start1,start2,finish1,finish2;
	bool foundNum,neg;
	int left,right,num,counter;
	while(scanf("%d",&I)!=EOF)
	{
		str="";
		while(scanf("%c",&ch))
			if(ch=='(')
			break;
		str+='(';
		left=1;right=0;
		while(left!=right)
		{
			scanf("%c",&ch);
			if(ch!=' ' && ch!='\n')
			str+=ch;
			if(ch=='(')
			left+=1;
			if(ch==')')
			right+=1;
		}
		//cout<<str<<"\n";
		if(str[0]=='(' && str[1]==')')
		cout<<"no\n";
		else
		{
			PATHFOUND=0;
			int number = findnum(0);
			//left tree
			j=next_index;
			left=0;right=0;
			while(j<str.size() && str[j]!='(')
				j+=1;
			left=1;
			start1=j;
			j+=1;
			while(left!=right)
			{
				if(str[j]=='(')
				left+=1;
				if(str[j]==')')
				right+=1;
				j+=1;
			}
			finish1=j-1;
			left=1;right=0;
			start2=j;
			j+=1;
			while(left!=right)
			{
				if(str[j]=='(')
				left+=1;
				if(str[j]==')')
				right+=1;
				j+=1;
			}
			finish2=j-1;
			bool f1 = isEmpty(start1,finish1);
			bool f2 = isEmpty(start2,finish2);
			//cout<<f1<<" "<<f2<<"\n";
			//cout<<start1<<" "<<finish1<<" "<<start2<<" "<<finish2<<"\n";
			if(f1==1 && f2==1)
			{
				if(number==I)
				PATHFOUND=1;
				else
				PATHFOUND=0;
			}
			else if(f1)
			{
				calc(start2,finish2,number);
			}
			else if(f2)
			{
				calc(start1,finish1,number);
			}
			else
			{
				calc(start1,finish1,number);
				calc(start2,finish2,number);
			}

			if(PATHFOUND)
			cout<<"yes\n";
			else
			cout<<"no\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

int I;

string str;

int next_index;

bool PATHFOUND;

bool isEmpty(int a,int b)

{

if(a+1==b && str[a]=='(' && str[b]==')')

return 1;

return 0;

}

int findnum(int idx)

{

int numfoundAt=-1;

int num=0;

bool negative=false;

for(int i=idx;i<str.size();i++)

{

if(str[i]!='(' && str[i]!=')')

{

numfoundAt = i;

if(str[i]=='-')

negative = 1,

numfoundAt+=1;

break;

}

while( numfoundAt<str.size() && (str[numfoundAt]-'0')>=0 && (str[numfoundAt]-'0')<=9)

{

num*=10;

num+=(str[numfoundAt]-'0');

numfoundAt+=1;

}

if(negative)

num*=(-1);

next_index = numfoundAt;

return num;

}

//(5 (4 (11 (7()()) (2()()) ) () )

void calc(int a,int b,int sum)

{

int number = findnum(a);

int j=next_index;

int start1,start2,finish1,finish2;

int left=0,right=0;

while(j<str.size() && str[j]!='(')

j+=1;

left=1;

start1=j;

j+=1;

while(left!=right)

{

if(str[j]=='(')

left+=1;

if(str[j]==')')

right+=1;

j+=1;

}

finish1=j-1;

left=1;right=0;

start2=j;

j+=1;

while(left!=right)

{

if(str[j]=='(')

left+=1;

if(str[j]==')')

right+=1;

j+=1;

}

finish2=j-1;

bool f1 = isEmpty(start1,finish1);

bool f2 = isEmpty(start2,finish2);

if(f1==1 && f2==1)

{

if(sum+number==I)

{

PATHFOUND=1;

return;

}

else if(f1)

{

calc(start2,finish2,sum+number);

}

else if(f2)

{

calc(start1,finish1,sum+number);

}

else

{

calc(start1,finish1,sum+number);

calc(start2,finish2,sum+number);

}

//22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

int main()

{

char ch;

int j,start1,start2,finish1,finish2;

bool foundNum,neg;

int left,right,num,counter;

while(scanf("%d",&I)!=EOF)

{

str="";

while(scanf("%c",&ch))

if(ch=='(')

break;

str+='(';

left=1;right=0;

while(left!=right)

{

scanf("%c",&ch);

if(ch!=' ' && ch!='\n')

str+=ch;

if(ch=='(')

left+=1;

if(ch==')')

right+=1;

}

//cout<<str<<"\n";

if(str[0]=='(' && str[1]==')')

cout<<"no\n";

else

{

PATHFOUND=0;

int number = findnum(0);

//left tree

j=next_index;

left=0;right=0;

while(j<str.size() && str[j]!='(')

j+=1;

left=1;

start1=j;

j+=1;

while(left!=right)

{

if(str[j]=='(')

left+=1;

if(str[j]==')')

right+=1;

j+=1;

}

finish1=j-1;

left=1;right=0;

start2=j;

j+=1;

while(left!=right)

{

if(str[j]=='(')

left+=1;

if(str[j]==')')

right+=1;

j+=1;

}

finish2=j-1;

bool f1 = isEmpty(start1,finish1);

bool f2 = isEmpty(start2,finish2);

//cout<<f1<<" "<<f2<<"\n";

//cout<<start1<<" "<<finish1<<" "<<start2<<" "<<finish2<<"\n";

if(f1==1 && f2==1)

{

if(number==I)

PATHFOUND=1;

else

PATHFOUND=0;

}

else if(f1)

{

calc(start2,finish2,number);

}

else if(f2)

{

calc(start1,finish1,number);

}

else

{

calc(start1,finish1,number);

calc(start2,finish2,number);

}

if(PATHFOUND)

cout<<"yes\n";

else

cout<<"no\n";

}

return 0;

}

521

Asif NaeemNovember 20, 2015

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

int n,d,s;
int BusStartAtStop[51];
int BusRunAtRoad[51];
int gr[31][31];
bool visit[51][51];
vector<int> vRoadstops[21];
vector<int> vBusRunAtRoad[21];

void init()
{
	for(int i=0;i<51;i++)
	{
		BusStartAtStop[i]=0;
		BusRunAtRoad[i]=0;
	}
	for(int i=0;i<31;i++)
		for(int j=0;j<31;j++)
			gr[i][j]=0;
	for(int i=0;i<21;i++)
	{
		vRoadstops[i].clear();
		vBusRunAtRoad[i].clear();
	}
}

void floydwarshall()
{
	for(int k=1;k<=d;k++)
	{
		for(int i=1;i<=d;i++)
		{
			for(int j=1;j<=d;j++)
			{
				gr[i][j] = gr[i][j] | (gr[i][k] & gr[k][j]);
			}
		}
	}
}


bool bfs(int bus1,int bus2)
{
	int stop1,stop2;
	int nxtStop1,nxtStop2;
	int root1=BusRunAtRoad[bus1],root2=BusRunAtRoad[bus2];
	queue<int> q;
	memset(visit,false,sizeof(visit));
	q.push(BusStartAtStop[bus1]);
	q.push(BusStartAtStop[bus2]);
	visit[BusStartAtStop[bus1]][BusStartAtStop[bus2]]=1;
	while(!q.empty())
	{
		stop1 = q.front();q.pop();
		stop2 = q.front();q.pop();
		if(stop1==stop2)
		return 1;
		for(int i=0;i<vRoadstops[root1].size();i++)
		{
			if(vRoadstops[root1][i]==stop1)
			{
				nxtStop1 = vRoadstops[root1][(i+1)%vRoadstops[root1].size()];
				break;
			}
		}
		for(int i=0;i<vRoadstops[root2].size();i++)
		{
			if(vRoadstops[root2][i]==stop2)
			{
				nxtStop2 = vRoadstops[root2][(i+1)%vRoadstops[root2].size()];
				break;
			}
		}
		if(!visit[nxtStop1][nxtStop2])
		{
			visit[nxtStop1][nxtStop2]=1;
			q.push(nxtStop1);
			q.push(nxtStop2);
		}
	}
	return 0;
}

int main()
{
	string st;
	int a,b;
	bool f;
	int val,start,bus,ret;
	stringstream ss;
	while(getline(cin,st))
	{
		ss.clear();
		ss<<st;
		ss>>n;
		ss>>d;
		ss>>s;
		if(n+d+s==0)
			break;
		init();
		for(int i=1;i<=n;i++)
		{
			ss.clear();
			getline(cin,st);
			ss<<st;
			while(ss>>val)
			{
				vRoadstops[i].push_back(val);
			}
			ss.clear();
			getline(cin,st);
			ss<<st;
			while(ss>>start>>bus)
			{
				BusStartAtStop[bus]=start;
				BusRunAtRoad[bus]=i;
				vBusRunAtRoad[i].push_back(bus);
			}
		}

		for(int i=1;i<=d;i++)
		{
			for(int j=i+1;j<=d;j++)
			{
				if(bfs(i,j)==1)
				gr[i][j]=1,gr[j][i]=1;
			}
			gr[i][i]=1;
		}
		floydwarshall();
		f =1;
		for(int i=1;i<=d;i++)
		{
			for(int j=1;j<=d;j++)
			{
				if(gr[i][j]==0)
				f=0;
			}
			if(f==0)
			break;
		}
		if(f)
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

int n,d,s;

int BusStartAtStop[51];

int BusRunAtRoad[51];

int gr[31][31];

bool visit[51][51];

vector<int> vRoadstops[21];

vector<int> vBusRunAtRoad[21];

void init()

{

for(int i=0;i<51;i++)

{

BusStartAtStop[i]=0;

BusRunAtRoad[i]=0;

}

for(int i=0;i<31;i++)

for(int j=0;j<31;j++)

gr[i][j]=0;

for(int i=0;i<21;i++)

{

vRoadstops[i].clear();

vBusRunAtRoad[i].clear();

}

void floydwarshall()

{

for(int k=1;k<=d;k++)

{

for(int i=1;i<=d;i++)

{

for(int j=1;j<=d;j++)

{

gr[i][j] = gr[i][j] | (gr[i][k] & gr[k][j]);

}

bool bfs(int bus1,int bus2)

{

int stop1,stop2;

int nxtStop1,nxtStop2;

int root1=BusRunAtRoad[bus1],root2=BusRunAtRoad[bus2];

queue<int> q;

memset(visit,false,sizeof(visit));

q.push(BusStartAtStop[bus1]);

q.push(BusStartAtStop[bus2]);

visit[BusStartAtStop[bus1]][BusStartAtStop[bus2]]=1;

while(!q.empty())

{

stop1 = q.front();q.pop();

stop2 = q.front();q.pop();

if(stop1==stop2)

return 1;

for(int i=0;i<vRoadstops[root1].size();i++)

{

if(vRoadstops[root1][i]==stop1)

{

nxtStop1 = vRoadstops[root1][(i+1)%vRoadstops[root1].size()];

break;

}

for(int i=0;i<vRoadstops[root2].size();i++)

{

if(vRoadstops[root2][i]==stop2)

{

nxtStop2 = vRoadstops[root2][(i+1)%vRoadstops[root2].size()];

break;

}

if(!visit[nxtStop1][nxtStop2])

{

visit[nxtStop1][nxtStop2]=1;

q.push(nxtStop1);

q.push(nxtStop2);

}

return 0;

}

int main()

{

string st;

int a,b;

bool f;

int val,start,bus,ret;

stringstream ss;

while(getline(cin,st))

{

ss.clear();

ss<<st;

ss>>n;

ss>>d;

ss>>s;

if(n+d+s==0)

break;

init();

for(int i=1;i<=n;i++)

{

ss.clear();

getline(cin,st);

ss<<st;

while(ss>>val)

{

vRoadstops[i].push_back(val);

}

ss.clear();

getline(cin,st);

ss<<st;

while(ss>>start>>bus)

{

BusStartAtStop[bus]=start;

BusRunAtRoad[bus]=i;

vBusRunAtRoad[i].push_back(bus);

}

for(int i=1;i<=d;i++)

{

for(int j=i+1;j<=d;j++)

{

if(bfs(i,j)==1)

gr[i][j]=1,gr[j][i]=1;

}

gr[i][i]=1;

}

floydwarshall();

f =1;

for(int i=1;i<=d;i++)

{

for(int j=1;j<=d;j++)

{

if(gr[i][j]==0)

f=0;

}

if(f==0)

break;

}

if(f)

printf("Yes\n");

else

printf("No\n");

}

return 0;

}

794

Asif NaeemNovember 15, 2015

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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

#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;

}

710

Asif NaeemOctober 26, 2015

This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination.

#include <iostream>
#include <cstdio>
#include <climits>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

int w,h;
int SEGMENT;
int gr[80][80];
int visit[80][80];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs(int stx,int sty,int edx,int edy)
{
	int x,y,stp;
	int direction=0,tmpDirection;
	int tmpx,tmpy;
	queue<int> q;
	memset(visit,0,sizeof(visit));
	int step=0;
	q.push(stx);
	q.push(sty);
	q.push(step);
	q.push(direction);

	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		stp = q.front();q.pop();
		direction = q.front();q.pop();
		visit[x][y]=1;

		for(int i=0;i<4;i++)
		{
			if(x+dx[i]==edx && y+dy[i]==edy)
			{
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					return stp+1;
				return stp;
			}
			if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0)
			{
				tmpx = x+dx[i];
				tmpy = y+dy[i];
				q.push(x+dx[i]);
				q.push(y+dy[i]);
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					q.push(stp+1);
				else if(tmpDirection==direction)
					q.push(stp);
				q.push(tmpDirection);
			}
		}
	}
	return -1;
}


int main()
{
	char ch;
	int kase=1;
	string str;
	vector<int> path;
	int x1,x2,y1,y2;
	while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h)
	{
		memset(gr,0,sizeof(gr));
		for(int i=1;i<=h;i++)
		{
			getline(cin,str);
			for(int j=0;j<w;j++)
			{
				if(str[j]=='X')
				gr[i][j+1]=1;
				else if(str[j]==' ')
				gr[i][j+1]=0;
			}
		}
		bool flag=0;
		int ccase=1;
		int res;
		while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch))
		{
			if(x1+y1+x2+y2==0)
			break;
			res = bfs(y1,x1,y2,x2);
			if(flag==0)
				printf("Board #%d:\n",kase++);
			flag = 1;
			if(res==-1)
			printf("Pair %d: impossible.\n",ccase++);
			else
			printf("Pair %d: %d segments.\n",ccase++,res);
		}
		printf("\n");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <iostream>

#include <cstdio>

#include <climits>

#include <queue>

#include <cstring>

#include <string>

using namespace std;

int w,h;

int SEGMENT;

int gr[80][80];

int visit[80][80];

int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};

int bfs(int stx,int sty,int edx,int edy)

{

int x,y,stp;

int direction=0,tmpDirection;

int tmpx,tmpy;

queue<int> q;

memset(visit,0,sizeof(visit));

int step=0;

q.push(stx);

q.push(sty);

q.push(step);

q.push(direction);

while(!q.empty())

{

x = q.front();q.pop();

y = q.front();q.pop();

stp = q.front();q.pop();

direction = q.front();q.pop();

visit[x][y]=1;

for(int i=0;i<4;i++)

{

if(x+dx[i]==edx && y+dy[i]==edy)

{

if(dx[i]==0)

tmpDirection=1;//horizontal direction

else if(dy[i]==0)

tmpDirection=2;//vertical direction

if(tmpDirection!=direction)

return stp+1;

return stp;

}

if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0)

{

tmpx = x+dx[i];

tmpy = y+dy[i];

q.push(x+dx[i]);

q.push(y+dy[i]);

if(dx[i]==0)

tmpDirection=1;//horizontal direction

else if(dy[i]==0)

tmpDirection=2;//vertical direction

if(tmpDirection!=direction)

q.push(stp+1);

else if(tmpDirection==direction)

q.push(stp);

q.push(tmpDirection);

}

return -1;

}

int main()

{

char ch;

int kase=1;

string str;

vector<int> path;

int x1,x2,y1,y2;

while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h)

{

memset(gr,0,sizeof(gr));

for(int i=1;i<=h;i++)

{

getline(cin,str);

for(int j=0;j<w;j++)

{

if(str[j]=='X')

gr[i][j+1]=1;

else if(str[j]==' ')

gr[i][j+1]=0;

}

bool flag=0;

int ccase=1;

int res;

while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch))

{

if(x1+y1+x2+y2==0)

break;

res = bfs(y1,x1,y2,x2);

if(flag==0)

printf("Board #%d:\n",kase++);

flag = 1;

if(res==-1)

printf("Pair %d: impossible.\n",ccase++);

else

printf("Pair %d: %d segments.\n",ccase++,res);

}

printf("\n");

}

return 0;

}

633

Asif NaeemOctober 24, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

int stx,sty,edx,edy;
int gr[405][405];
int dirx[8]={-2,-2,2,2,1,1,-1,-1};
int diry[8]={1,-1,1,-1,2,-2,2,-2};
int dx[4]={2,2,-2,-2};
int dy[4]={-2,2,2,-2};
int n;

int bfs()
{
	queue<int> q;
	int x,y;
	//int visit[405][405];
	//memset(visit,0,sizeof(visit));
	int moveTyp=0,move;
	int step=0,stepCount;
	q.push(stx);q.push(sty);q.push(moveTyp);q.push(step);
	if(gr[stx][sty]==1)
	return -1;
	else if(gr[edx][edy]==1)
	return -1;

	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		moveTyp = q.front();q.pop();
		stepCount = q.front();q.pop();
		gr[x][y]=1;
		if(x==edx && y==edy)
		{
			return stepCount;
		}
		if(moveTyp==0)
		{
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
		}
		else if(moveTyp==1)
		{
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
		}
		else if(moveTyp==2)
		{
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
		}
		else if(moveTyp==3)
		{
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
		}
	}
	return -1;
}
int main()
{
	int a,b;
	while(scanf("%d",&n),n)
	{
		scanf("%d%d",&stx,&sty);
		scanf("%d%d",&edx,&edy);
		memset(gr,0,sizeof(gr));
		while(scanf("%d%d",&a,&b),a,b)
		{
			gr[a][b]=1;
		}
		int ret = bfs();
		if(ret==-1)
		{
			printf("Solution doesn't exist\n");
		}
		else
		printf("Result : %d\n",ret);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <queue>

using namespace std;

int stx,sty,edx,edy;

int gr[405][405];

int dirx[8]={-2,-2,2,2,1,1,-1,-1};

int diry[8]={1,-1,1,-1,2,-2,2,-2};

int dx[4]={2,2,-2,-2};

int dy[4]={-2,2,2,-2};

int n;

int bfs()

{

queue<int> q;

int x,y;

//int visit[405][405];

//memset(visit,0,sizeof(visit));

int moveTyp=0,move;

int step=0,stepCount;

q.push(stx);q.push(sty);q.push(moveTyp);q.push(step);

if(gr[stx][sty]==1)

return -1;

else if(gr[edx][edy]==1)

return -1;

while(!q.empty())

{

x = q.front();q.pop();

y = q.front();q.pop();

moveTyp = q.front();q.pop();

stepCount = q.front();q.pop();

gr[x][y]=1;

if(x==edx && y==edy)

{

return stepCount;

}

if(moveTyp==0)

{

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

else if(moveTyp==1)

{

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

else if(moveTyp==2)

{

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

else if(moveTyp==3)

{

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

return -1;

}

int main()

{

int a,b;

while(scanf("%d",&n),n)

{

scanf("%d%d",&stx,&sty);

scanf("%d%d",&edx,&edy);

memset(gr,0,sizeof(gr));

while(scanf("%d%d",&a,&b),a,b)

{

gr[a][b]=1;

}

int ret = bfs();

if(ret==-1)

{

printf("Solution doesn't exist\n");

}

else

printf("Result : %d\n",ret);

}

return 0;

}

627

Asif NaeemOctober 24, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

vector<int> vb[305];
vector<int> par;

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}

int main()
{
	int router,qry;
	int fr,to,st,ed,i;
	string str;
	while(scanf("%d",&router)!=EOF)
	{
		getchar();
		for(int II=0;II<305;II++)
		vb[II].clear();
		for(int II=0;II<router;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			i+=1;
			to=0;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					vb[fr].push_back(to);
					to=0;
					i+=1;
				}
				else
				{
					to *= 10;
					to += (str[i++]-'0');
				}
			}
			vb[fr].push_back(to);
		}
		scanf("%d",&qry);
		for(int II=0;II<qry;II++)
		{
			scanf("%d%d",&st,&ed);
			int *path = new int[router+5];
			for(int JJ=0;JJ<router+5;JJ++)
			path[JJ]=JJ;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				//cout<<"path = "<<path[5]<<"\n";
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",par[LL],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <cstdio>

#include <sstream>

#include <vector>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

vector<int> vb[305];

vector<int> par;

bool bfs(int path[],int st,int ed)

{

int visit[400];

for(int i=0;i<400;i++)

visit[i]=0;

queue<int> q;

q.push(st);

visit[st]=1;

int a,b;

if(st==ed)

return 1;

while(!q.empty())

{

a = q.front();q.pop();

if(a==ed)

return 1;

for(int i=0;i<vb[a].size();i++)

{

b = vb[a][i];

if(visit[b]==0)

{

visit[b]=1;

q.push(b);

path[b]=a;

}

return 0;

}

int main()

{

int router,qry;

int fr,to,st,ed,i;

string str;

while(scanf("%d",&router)!=EOF)

{

getchar();

for(int II=0;II<305;II++)

vb[II].clear();

for(int II=0;II<router;II++)

{

getline(cin,str);

i=0;

fr=0;

while(str[i]!='-')

{

fr *= 10;fr += (str[i++]-'0');

}

i+=1;

to=0;

while(i<str.size())

{

if(str[i]==',')

{

vb[fr].push_back(to);

to=0;

i+=1;

}

else

{

to *= 10;

to += (str[i++]-'0');

}

vb[fr].push_back(to);

}

scanf("%d",&qry);

for(int II=0;II<qry;II++)

{

scanf("%d%d",&st,&ed);

int *path = new int[router+5];

for(int JJ=0;JJ<router+5;JJ++)

path[JJ]=JJ;

bool f = bfs(path,st,ed);

if(II==0)

printf("-----\n");

if(!f)

printf("connection impossible\n");

else

{

//cout<<"path = "<<path[5]<<"\n";

int cc = ed;

par.clear();

while(path[cc]!=cc)

{

par.push_back(cc);

cc=path[cc];

}

par.push_back(cc);

for(int LL=par.size()-1;LL>=0;LL--)

printf("%d%s",par[LL],LL==0?"\n":" ");

}

delete path;

}

return 0;

}

There is another solution using Linked List in case Router ID is not limited from 1 to 300. But for this problem this solution gets TLE.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

struct Node{
	int number;
	Node *next;
};
struct Edge{
	int from,to;
	Edge *next;
	Edge(int f,int t);
};

Node *nodeList=0;
Edge *edgeList=0;
int IndexOfId[400];
vector<int> vb[400];
vector<int> par;

int GetNodeIndex(int num)
{
	Node *p=nodeList;
	int idx=0;
	while(p->next)
	{
		p=p->next;
		if(p->number==num)
		return idx;
		idx+=1;
	}
	p->next=new Node();
	p=p->next;
	p->number=num;
	p->next=0;
	IndexOfId[idx]=num;
	return idx;
}

Edge::Edge(int f,int t)
{
	from = f;
	to = t;
}

void init()
{
	Node *p=nodeList,*q;
	memset(IndexOfId,0,sizeof(IndexOfId));
	while(p)
	{
		q = p;
		p = p->next;
		delete q;
	}
	nodeList = new Node();
	nodeList->next=0;
	nodeList->number=-100;

	Edge *pp=edgeList,*tmp;
	while(pp)
	{
		tmp=pp;
		pp=pp->next;
		delete tmp;
	}
}

int CountNode()
{
	Node *p=nodeList->next;
	int cnt=0;
	while(p)
	{
		cnt+=1;
		p=p->next;
	}
	return cnt;
}

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}
int main()
{
	int n,m,fr,to,i;
	int a,b;
	string str;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		init();
		for(int II=0;II<n;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			fr = GetNodeIndex(fr);
			to=0;
			i+=1;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					to = GetNodeIndex(to);
					Edge *e=new Edge(fr,to);
					e->next = edgeList;
					edgeList = e;
					to=0;
					i+=1;
				}
				else
				{
					to *= 10; to += (str[i++]-'0');
				}
			}
			to = GetNodeIndex(to);
			Edge *e=new Edge(fr,to);
			e->next = edgeList;
			edgeList = e;

		}
		int nodeCount = CountNode();
		for(int II=0;II<400;II++)
			vb[II].clear();
		Edge *tmpEdge=edgeList;
		while(tmpEdge)
		{
			a = tmpEdge->from;
			b = tmpEdge->to;
			vb[a].push_back(b);
			tmpEdge=tmpEdge->next;
		}
		scanf("%d",&m);
		for(int II=0;II<m;II++)
		{
			int st,ed;
			scanf("%d%d",&st,&ed);
			st=GetNodeIndex(st);
			ed=GetNodeIndex(ed);
			int *path = new int[nodeCount];
			for(int KK=0;KK<nodeCount;KK++)
			path[KK]=KK;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",IndexOfId[par[LL]],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

#include <iostream>

#include <cstdio>

#include <sstream>

#include <vector>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

struct Node{

int number;

Node *next;

};

struct Edge{

int from,to;

Edge *next;

Edge(int f,int t);

};

Node *nodeList=0;

Edge *edgeList=0;

int IndexOfId[400];

vector<int> vb[400];

vector<int> par;

int GetNodeIndex(int num)

{

Node *p=nodeList;

int idx=0;

while(p->next)

{

p=p->next;

if(p->number==num)

return idx;

idx+=1;

}

p->next=new Node();

p=p->next;

p->number=num;

p->next=0;

IndexOfId[idx]=num;

return idx;

}

Edge::Edge(int f,int t)

{

from = f;

to = t;

}

void init()

{

Node *p=nodeList,*q;

memset(IndexOfId,0,sizeof(IndexOfId));

while(p)

{

q = p;

p = p->next;

delete q;

}

nodeList = new Node();

nodeList->next=0;

nodeList->number=-100;

Edge *pp=edgeList,*tmp;

while(pp)

{

tmp=pp;

pp=pp->next;

delete tmp;

}

int CountNode()

{

Node *p=nodeList->next;

int cnt=0;

while(p)

{

cnt+=1;

p=p->next;

}

return cnt;

}

bool bfs(int path[],int st,int ed)

{

int visit[400];

for(int i=0;i<400;i++)

visit[i]=0;

queue<int> q;

q.push(st);

visit[st]=1;

int a,b;

if(st==ed)

return 1;

while(!q.empty())

{

a = q.front();q.pop();

if(a==ed)

return 1;

for(int i=0;i<vb[a].size();i++)

{

b = vb[a][i];

if(visit[b]==0)

{

visit[b]=1;

q.push(b);

path[b]=a;

}

return 0;

}

int main()

{

int n,m,fr,to,i;

int a,b;

string str;

while(scanf("%d",&n)!=EOF)

{

getchar();

init();

for(int II=0;II<n;II++)

{

getline(cin,str);

i=0;

fr=0;

while(str[i]!='-')

{

fr *= 10;fr += (str[i++]-'0');

}

fr = GetNodeIndex(fr);

to=0;

i+=1;

while(i<str.size())

{

if(str[i]==',')

{

to = GetNodeIndex(to);

Edge *e=new Edge(fr,to);

e->next = edgeList;

edgeList = e;

to=0;

i+=1;

}

else

{

to *= 10; to += (str[i++]-'0');

}

to = GetNodeIndex(to);

Edge *e=new Edge(fr,to);

e->next = edgeList;

edgeList = e;

}

int nodeCount = CountNode();

for(int II=0;II<400;II++)

vb[II].clear();

Edge *tmpEdge=edgeList;

while(tmpEdge)

{

a = tmpEdge->from;

b = tmpEdge->to;

vb[a].push_back(b);

tmpEdge=tmpEdge->next;

}

scanf("%d",&m);

for(int II=0;II<m;II++)

{

int st,ed;

scanf("%d%d",&st,&ed);

st=GetNodeIndex(st);

ed=GetNodeIndex(ed);

int *path = new int[nodeCount];

for(int KK=0;KK<nodeCount;KK++)

path[KK]=KK;

bool f = bfs(path,st,ed);

if(II==0)

printf("-----\n");

if(!f)

printf("connection impossible\n");

else

{

int cc = ed;

par.clear();

while(path[cc]!=cc)

{

par.push_back(cc);

cc=path[cc];

}

par.push_back(cc);

for(int LL=par.size()-1;LL>=0;LL--)

printf("%d%s",IndexOfId[par[LL]],LL==0?"\n":" ");

}

delete path;

}

return 0;

}

599

Asif NaeemOctober 22, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
int parent[26];
int countNodes[26];

int getparent(int n)
{
	if(parent[n]==n)
	return n;
	else
	return parent[n]=getparent(parent[n]);
}

void unite(int a,int b)
{
	parent[getparent(a)]=getparent(b);
}
int main()
{
	int t;
	string str;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		str="";
		for(int i=0;i<26;i++)
		{
			parent[i]=i;
			countNodes[i]=0;
		}
		while(getline(cin,str),str[0]!='*')
		{
			unite(str[1]-'A',str[3]-'A');
		}
		getline(cin,str);
		for(int i=0;i<str.size();i++)
		{
			if(str[i]!=',')
			countNodes[getparent(str[i]-'A')]+=1;
		}
		int tree=0,acron=0;
		for(int i=0;i<26;i++)
		{
			if(countNodes[i]>1)
			tree+=1;
			else if(countNodes[i]==1)
			acron+=1;
		}
		printf("There are %d tree(s) and %d acorn(s).\n",tree,acron);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

int parent[26];

int countNodes[26];

int getparent(int n)

{

if(parent[n]==n)

return n;

else

return parent[n]=getparent(parent[n]);

}

void unite(int a,int b)

{

parent[getparent(a)]=getparent(b);

}

int main()

{

int t;

string str;

scanf("%d",&t);

getchar();

while(t--)

{

str="";

for(int i=0;i<26;i++)

{

parent[i]=i;

countNodes[i]=0;

}

while(getline(cin,str),str[0]!='*')

{

unite(str[1]-'A',str[3]-'A');

}

getline(cin,str);

for(int i=0;i<str.size();i++)

{

if(str[i]!=',')

countNodes[getparent(str[i]-'A')]+=1;

}

int tree=0,acron=0;

for(int i=0;i<26;i++)

{

if(countNodes[i]>1)

tree+=1;

else if(countNodes[i]==1)

acron+=1;

}

printf("There are %d tree(s) and %d acorn(s).\n",tree,acron);

}

return 0;

}

Category: Graph Algorithm

10986

10336

112

521

794

710

633

627

599

Archives

Categories