DFS AND BFS – Live with passion

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;

}

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;

}

321

Asif NaeemOctober 6, 2015

I used bit operation to represent the states of the switches state of the villa.

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

using namespace std;

struct Point{
	int x,y;
};
int kase=1;
Point points[11500];
int arr[11][1024];
int array_map_par[11500];
bool door[15][15];
bool light_swtch[15][15];
bool flag;
int RR,DD,SS;
int gr[11][1024];

int checkbit(int num,int idx)
{
	return (num&(1<<(idx-1)));
}
void bfs()
{
	int bit;
	vector<string> vb;
	string str[11500];
	queue<int> q;
	int step;
	gr[1][1]=1;
	q.push(1);q.push(1);q.push(0);
	while(!q.empty())
	{
		int rum=q.front();q.pop();
		int res=q.front();q.pop();
		int status_vila = res;
		int num=res;
		int parent_index = arr[rum][res];
		step=q.front();q.pop();
		if(rum==RR && res==(1<<(RR-1)))
		{
			printf("Villa #%d\nThe problem can be solved in %d steps:\n",kase++,step);

			flag=1;
			while(array_map_par[parent_index]!=-1)
			{
				vb.push_back(str[parent_index]);
				parent_index = array_map_par[parent_index];
			}
			for(int II=vb.size()-1;II>=0;II--)
			cout<<vb[II];
			return;
		}
		for(int i=1;i<=RR;i++)
		{
			if(light_swtch[rum][i])
			{
				bit=checkbit(res,i);
				if(bit==0)
				{
					status_vila = res | (1<<(i-1));
					if(gr[rum][status_vila]==0)
					{
						gr[rum][status_vila]=1;
						q.push(rum);q.push(status_vila);
						q.push(step+1);
						array_map_par[arr[rum][status_vila]]=parent_index;
						str[arr[rum][status_vila]]="- Switch on light in room ";
						if(i<10)
						str[arr[rum][status_vila]].append(1u,char(i+'0'));
						else
							str[arr[rum][status_vila]].append("10");
						str[arr[rum][status_vila]].append(".\n");
					}
				}
				else
				{
					status_vila = res & (~(1<<(i-1)));
					if(gr[rum][status_vila]==0 && rum!=i)//cant switch off the room where he is in
					{
						gr[rum][status_vila]=1;
						q.push(rum);q.push(status_vila);
						q.push(step+1);
						array_map_par[arr[rum][status_vila]]=parent_index;
						str[arr[rum][status_vila]]="- Switch off light in room ";
						if(i<10)
							str[arr[rum][status_vila]].append(1u,char(i+'0'));
						else
							str[arr[rum][status_vila]].append("10");
						str[arr[rum][status_vila]].append(".\n");
					}
				}

			}
		}
		int rum_index=0;
		while(num)
		{
			rum_index+=1;
			bit = (num&1);
			num=(num>>1);
			if(door[rum][rum_index]==0)
			continue;
			if(bit)
			{
				if(gr[rum_index][res]==0)
				{
					gr[rum_index][res]=1;
					q.push(rum_index);q.push(res);
					q.push(step+1);
					array_map_par[arr[rum_index][res]]=parent_index;
					str[arr[rum_index][res]]="- Move to room ";
					if(rum_index<10)
					str[arr[rum_index][res]].append(1u,char(rum_index+'0'));
					else
					str[arr[rum_index][res]].append("10");
					str[arr[rum_index][res]].append(".\n");

				}
			}
		}

	}

}

void _init()
{
	int cnt=1;
	for(int i=1;i<11;i++)
	{
		for(int j=1;j<1024;j++)
		{
			points[cnt].x=i;points[cnt].y=j;
			arr[i][j]=cnt;cnt+=1;
		}
	}
}
int main()
{
	int a,b;
	_init();
	while(scanf("%d%d%d",&RR,&DD,&SS))
	{
		if(RR+DD+SS==0)
		break;
		memset(door,0,sizeof(door));
		memset(gr,0,sizeof(gr));
		memset(light_swtch,0,sizeof(light_swtch));
		memset(array_map_par,-1,sizeof(array_map_par));

		for(int i=1;i<=DD;i++)
		{
			scanf("%d%d",&a,&b);door[a][b]=1;door[b][a]=1;
		}
		for(int i=1;i<=SS;i++)
		{
			scanf("%d%d",&a,&b);light_swtch[a][b]=1;
		}
		flag=0;
		bfs();
		if(!flag)
		printf("Villa #%d\nThe problem cannot be solved.\n\n",kase++);
		else
		printf("\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

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

struct Point{

int x,y;

};

int kase=1;

Point points[11500];

int arr[11][1024];

int array_map_par[11500];

bool door[15][15];

bool light_swtch[15][15];

bool flag;

int RR,DD,SS;

int gr[11][1024];

int checkbit(int num,int idx)

{

return (num&(1<<(idx-1)));

}

void bfs()

{

int bit;

vector<string> vb;

string str[11500];

queue<int> q;

int step;

gr[1][1]=1;

q.push(1);q.push(1);q.push(0);

while(!q.empty())

{

int rum=q.front();q.pop();

int res=q.front();q.pop();

int status_vila = res;

int num=res;

int parent_index = arr[rum][res];

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

if(rum==RR && res==(1<<(RR-1)))

{

printf("Villa #%d\nThe problem can be solved in %d steps:\n",kase++,step);

flag=1;

while(array_map_par[parent_index]!=-1)

{

vb.push_back(str[parent_index]);

parent_index = array_map_par[parent_index];

}

for(int II=vb.size()-1;II>=0;II--)

cout<<vb[II];

return;

}

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

{

if(light_swtch[rum][i])

{

bit=checkbit(res,i);

if(bit==0)

{

status_vila = res | (1<<(i-1));

if(gr[rum][status_vila]==0)

{

gr[rum][status_vila]=1;

q.push(rum);q.push(status_vila);

q.push(step+1);

array_map_par[arr[rum][status_vila]]=parent_index;

str[arr[rum][status_vila]]="- Switch on light in room ";

if(i<10)

str[arr[rum][status_vila]].append(1u,char(i+'0'));

else

str[arr[rum][status_vila]].append("10");

str[arr[rum][status_vila]].append(".\n");

}

else

{

status_vila = res & (~(1<<(i-1)));

if(gr[rum][status_vila]==0 && rum!=i)//cant switch off the room where he is in

{

gr[rum][status_vila]=1;

q.push(rum);q.push(status_vila);

q.push(step+1);

array_map_par[arr[rum][status_vila]]=parent_index;

str[arr[rum][status_vila]]="- Switch off light in room ";

if(i<10)

str[arr[rum][status_vila]].append(1u,char(i+'0'));

else

str[arr[rum][status_vila]].append("10");

str[arr[rum][status_vila]].append(".\n");

}

int rum_index=0;

while(num)

{

rum_index+=1;

bit = (num&1);

num=(num>>1);

if(door[rum][rum_index]==0)

continue;

if(bit)

{

if(gr[rum_index][res]==0)

{

gr[rum_index][res]=1;

q.push(rum_index);q.push(res);

q.push(step+1);

array_map_par[arr[rum_index][res]]=parent_index;

str[arr[rum_index][res]]="- Move to room ";

if(rum_index<10)

str[arr[rum_index][res]].append(1u,char(rum_index+'0'));

else

str[arr[rum_index][res]].append("10");

str[arr[rum_index][res]].append(".\n");

}

void _init()

{

int cnt=1;

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

{

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

{

points[cnt].x=i;points[cnt].y=j;

arr[i][j]=cnt;cnt+=1;

}

int main()

{

int a,b;

_init();

while(scanf("%d%d%d",&RR,&DD,&SS))

{

if(RR+DD+SS==0)

break;

memset(door,0,sizeof(door));

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

memset(light_swtch,0,sizeof(light_swtch));

memset(array_map_par,-1,sizeof(array_map_par));

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

{

scanf("%d%d",&a,&b);door[a][b]=1;door[b][a]=1;

}

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

{

scanf("%d%d",&a,&b);light_swtch[a][b]=1;

}

flag=0;

bfs();

if(!flag)

printf("Villa #%d\nThe problem cannot be solved.\n\n",kase++);

else

printf("\n");

}

return 0;

}

314

Asif NaeemSeptember 23, 2015

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

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3

using namespace std;

struct State{
	int x,y,dir;
	int val;
};

int r,c;
int gr[55][55][4];
string face;
int bx,by,ex,ey;

void bfs()
{
	int dir;
	queue<int> q;
	if(face=="south")
	dir=SOUTH;
	else if(face=="north")
	dir=NORTH;
	else if(face=="east")
	dir=EAST;
	else if(face=="west")
	dir=WEST;
	q.push(bx);q.push(by);q.push(dir);q.push(0);
	int x,y,d,v;
	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		d = q.front();q.pop();
		v = q.front();q.pop();
		//cout<<x<<" "<<y<<"\n";
		gr[x][y][d]=1;
		if(ex==x && ey==y)
		{
			printf("%d\n",v);return;
		}
		if(d==NORTH)
		{
			if(gr[x][y][WEST]==0)
			{
				q.push(x);q.push(y);
				q.push(WEST);
				q.push(v+1);
			}
			if(gr[x][y][EAST]==0)
			{
				q.push(x);q.push(y);
				q.push(EAST);
				q.push(v+1);
			}

			if(x-1>0 && gr[x-1][y][d]==0)
			{
				q.push(x-1);q.push(y);q.push(d);
				q.push(v+1);
			}
			if(x-2>0 && gr[x-2][y][d]==0 && gr[x-1][y][d]==0)
			{
				q.push(x-2);q.push(y);q.push(d);
				q.push(v+1);
			}
			if(x-3>0 && gr[x-3][y][d]==0 && gr[x-2][y][d]==0 && gr[x-1][y][d]==0)
			{
				q.push(x-3);q.push(y);q.push(d);
				q.push(v+1);
			}
		}
		else if(d==EAST)
		{
			if(gr[x][y][NORTH]==0)
			{
				q.push(x);q.push(y);
				q.push(NORTH);
				q.push(v+1);
			}
			if(gr[x][y][SOUTH]==0)
			{
				q.push(x);q.push(y);
				q.push(SOUTH);
				q.push(v+1);
			}

			if(y+1<c && gr[x][y+1][d]==0)
			{
				q.push(x);q.push(y+1);q.push(d);
				q.push(v+1);
			}
			if(y+2<c && gr[x][y+2][d]==0 && gr[x][y+1][d]==0)
			{
				q.push(x);q.push(y+2);q.push(d);
				q.push(v+1);
			}
			if(y+3<c && gr[x][y+3][d]==0 && gr[x][y+2][d]==0 && gr[x][y+1][d]==0)
			{
				q.push(x);q.push(y+3);q.push(d);
				q.push(v+1);
			}
		}
		else if(d==WEST)
		{
			if(gr[x][y][NORTH]==0)
			{
				q.push(x);q.push(y);
				q.push(NORTH);
				q.push(v+1);
			}
			if(gr[x][y][SOUTH]==0)
			{
				q.push(x);q.push(y);
				q.push(SOUTH);
				q.push(v+1);
			}

			if(y-1>0 && gr[x][y-1][d]==0)
			{
				q.push(x);q.push(y-1);q.push(d);
				q.push(v+1);
			}
			if(y-2>0 && gr[x][y-2][d]==0 && gr[x][y-1][d]==0)
			{
				q.push(x);q.push(y-2);q.push(d);
				q.push(v+1);
			}
			if(y-3>0 && gr[x][y-3][d]==0 && gr[x][y-2][d]==0 && gr[x][y-1][d]==0)
			{
				q.push(x);q.push(y-3);q.push(d);
				q.push(v+1);
			}
		}
		else if(d==SOUTH)
		{
			if(gr[x][y][WEST]==0)
			{
				q.push(x);q.push(y);
				q.push(WEST);
				q.push(v+1);
			}
			if(gr[x][y][EAST]==0)
			{
				q.push(x);q.push(y);
				q.push(EAST);
				q.push(v+1);
			}

			if(x+1<r && gr[x+1][y][d]==0)
			{
				q.push(x+1);q.push(y);q.push(d);
				q.push(v+1);
			}
			if(x+2<r && gr[x+2][y][d]==0 && gr[x+1][y][d]==0)
			{
				q.push(x+2);q.push(y);q.push(d);
				q.push(v+1);
			}
			if(x+3<r && gr[x+3][y][d]==0 && gr[x+2][y][d]==0 && gr[x+1][y][d]==0)
			{
				q.push(x+3);q.push(y);q.push(d);
				q.push(v+1);
			}
		}


	}
	printf("-1\n");return;
}

int main()
{
	int a;
	while(scanf("%d%d",&r,&c))
	{
		if(r+c==0)
		break;
		memset(gr,0,sizeof(gr));

		for(int i=0;i<r;i++)
		{
			for(int j=0;j<c;j++)
				{
					scanf("%d",&a);
					if(a)
					{
						for(int k=0;k<4;k++)
						{
							gr[i][j][k]=a;gr[i+1][j+1][k]=a;
							gr[i+1][j][k]=a;gr[i][j+1][k]=a;
						}
					}
				}
		}
		scanf("%d%d%d%d",&bx,&by,&ex,&ey);
		cin>>face;
		bfs();
	}
	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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <string>

#define NORTH 0

#define EAST 1

#define SOUTH 2

#define WEST 3

using namespace std;

struct State{

int x,y,dir;

int val;

};

int r,c;

int gr[55][55][4];

string face;

int bx,by,ex,ey;

void bfs()

{

int dir;

queue<int> q;

if(face=="south")

dir=SOUTH;

else if(face=="north")

dir=NORTH;

else if(face=="east")

dir=EAST;

else if(face=="west")

dir=WEST;

q.push(bx);q.push(by);q.push(dir);q.push(0);

int x,y,d,v;

while(!q.empty())

{

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

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

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

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

//cout<<x<<" "<<y<<"\n";

gr[x][y][d]=1;

if(ex==x && ey==y)

{

printf("%d\n",v);return;

}

if(d==NORTH)

{

if(gr[x][y][WEST]==0)

{

q.push(x);q.push(y);

q.push(WEST);

q.push(v+1);

}

if(gr[x][y][EAST]==0)

{

q.push(x);q.push(y);

q.push(EAST);

q.push(v+1);

}

if(x-1>0 && gr[x-1][y][d]==0)

{

q.push(x-1);q.push(y);q.push(d);

q.push(v+1);

}

if(x-2>0 && gr[x-2][y][d]==0 && gr[x-1][y][d]==0)

{

q.push(x-2);q.push(y);q.push(d);

q.push(v+1);

}

if(x-3>0 && gr[x-3][y][d]==0 && gr[x-2][y][d]==0 && gr[x-1][y][d]==0)

{

q.push(x-3);q.push(y);q.push(d);

q.push(v+1);

}

else if(d==EAST)

{

if(gr[x][y][NORTH]==0)

{

q.push(x);q.push(y);

q.push(NORTH);

q.push(v+1);

}

if(gr[x][y][SOUTH]==0)

{

q.push(x);q.push(y);

q.push(SOUTH);

q.push(v+1);

}

if(y+1<c && gr[x][y+1][d]==0)

{

q.push(x);q.push(y+1);q.push(d);

q.push(v+1);

}

if(y+2<c && gr[x][y+2][d]==0 && gr[x][y+1][d]==0)

{

q.push(x);q.push(y+2);q.push(d);

q.push(v+1);

}

if(y+3<c && gr[x][y+3][d]==0 && gr[x][y+2][d]==0 && gr[x][y+1][d]==0)

{

q.push(x);q.push(y+3);q.push(d);

q.push(v+1);

}

else if(d==WEST)

{

if(gr[x][y][NORTH]==0)

{

q.push(x);q.push(y);

q.push(NORTH);

q.push(v+1);

}

if(gr[x][y][SOUTH]==0)

{

q.push(x);q.push(y);

q.push(SOUTH);

q.push(v+1);

}

if(y-1>0 && gr[x][y-1][d]==0)

{

q.push(x);q.push(y-1);q.push(d);

q.push(v+1);

}

if(y-2>0 && gr[x][y-2][d]==0 && gr[x][y-1][d]==0)

{

q.push(x);q.push(y-2);q.push(d);

q.push(v+1);

}

if(y-3>0 && gr[x][y-3][d]==0 && gr[x][y-2][d]==0 && gr[x][y-1][d]==0)

{

q.push(x);q.push(y-3);q.push(d);

q.push(v+1);

}

else if(d==SOUTH)

{

if(gr[x][y][WEST]==0)

{

q.push(x);q.push(y);

q.push(WEST);

q.push(v+1);

}

if(gr[x][y][EAST]==0)

{

q.push(x);q.push(y);

q.push(EAST);

q.push(v+1);

}

if(x+1<r && gr[x+1][y][d]==0)

{

q.push(x+1);q.push(y);q.push(d);

q.push(v+1);

}

if(x+2<r && gr[x+2][y][d]==0 && gr[x+1][y][d]==0)

{

q.push(x+2);q.push(y);q.push(d);

q.push(v+1);

}

if(x+3<r && gr[x+3][y][d]==0 && gr[x+2][y][d]==0 && gr[x+1][y][d]==0)

{

q.push(x+3);q.push(y);q.push(d);

q.push(v+1);

}

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

}

int main()

{

int a;

while(scanf("%d%d",&r,&c))

{

if(r+c==0)

break;

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

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

{

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

{

scanf("%d",&a);

if(a)

{

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

{

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

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

}

scanf("%d%d%d%d",&bx,&by,&ex,&ey);

cin>>face;

bfs();

}

return 0;

}

298

Asif NaeemSeptember 21, 2015

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

using namespace std;

bool gr[30][30][7][7];
//bool gr2D[30][30];

struct Point{
	int x,y,velocity,accleration;
	int val;
};
Point St,Fn;
int m,n;

void bfs()
{
	int x,y,v,a,val;
	int dx,dy,tx,ty;
	queue<int> q;
	q.push(St.x);q.push(St.y);
	q.push(0);q.push(0);q.push(0);
	gr[St.x][St.y][0+3][0+3]=1;

	while(!q.empty())
	{
		x=q.front();q.pop();
		y=q.front();q.pop();
		v=q.front();q.pop();
		a=q.front();q.pop();
		val = q.front();q.pop();
		//cout<<x<<" "<<y<<" "<<v<<" "<<a<<" "<<val<<"\n";
		if(x==Fn.x && y ==Fn.y)
		{
			printf("Optimal solution takes %d hops.\n", val);
			return;
		}
		for(int i=-1;i<=1;i++)
			for(int j=-1;j<=1;j++)
			{
				tx = v+i; ty = a+j;
				if(abs(tx)<=3 && abs(ty)<=3)
				{
					dx = x+v+i; dy = y+a+j;
					if(dx>=0 && dx<m && dy>=0 && dy<n && gr[dx][dy][tx+3][ty+3]==0)
					{
						//if(gr2D[dx][dy])
						//continue;
						gr[dx][dy][tx+3][ty+3]=1;
						q.push(dx); q.push(dy); q.push(tx); q.push(ty);
						q.push(val+1);
					}
				}
			}
	}
	printf("No solution.\n");
}

int main()
{
	int t,p;
	scanf("%d",&t);
	int x1,x2,y1,y2;
	Point A,B;
	while(t--)
	{
		scanf("%d%d",&m,&n);
		memset(gr,0,sizeof(gr));
		//memset(gr,0,sizeof(gr2D));
		scanf("%d%d%d%d",&St.x,&St.y,&Fn.x,&Fn.y);
		scanf("%d",&p);
		bool flag=1;
		while(p--)
		{
			scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
			for(int i=x1;i<=x2;i++)
			{
				for(int j=y1;j<=y2;j++)
				{
					//gr2D[i][j]=1;
					for(int k=0;k<7;k++)
					{
						for(int l=0;l<7;l++)
						{
							gr[i][j][k][l]=1;
							if(i==Fn.x && j==Fn.y)
								flag=0;
						}
					}
				}
			}
		}
		if(St.x==Fn.x && St.y==Fn.y)
		printf("Optimal solution takes 0 hops.\n");
		else
		{
			if(flag==0)
			printf("No solution.\n");
			else
			bfs();
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <cstdio>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

bool gr[30][30][7][7];

//bool gr2D[30][30];

struct Point{

int x,y,velocity,accleration;

int val;

};

Point St,Fn;

int m,n;

void bfs()

{

int x,y,v,a,val;

int dx,dy,tx,ty;

queue<int> q;

q.push(St.x);q.push(St.y);

q.push(0);q.push(0);q.push(0);

gr[St.x][St.y][0+3][0+3]=1;

while(!q.empty())

{

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

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

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

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

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

//cout<<x<<" "<<y<<" "<<v<<" "<<a<<" "<<val<<"\n";

if(x==Fn.x && y ==Fn.y)

{

printf("Optimal solution takes %d hops.\n", val);

return;

}

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

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

{

tx = v+i; ty = a+j;

if(abs(tx)<=3 && abs(ty)<=3)

{

dx = x+v+i; dy = y+a+j;

if(dx>=0 && dx<m && dy>=0 && dy<n && gr[dx][dy][tx+3][ty+3]==0)

{

//if(gr2D[dx][dy])

//continue;

gr[dx][dy][tx+3][ty+3]=1;

q.push(dx); q.push(dy); q.push(tx); q.push(ty);

q.push(val+1);

}

printf("No solution.\n");

}

int main()

{

int t,p;

scanf("%d",&t);

int x1,x2,y1,y2;

Point A,B;

while(t--)

{

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

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

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

scanf("%d%d%d%d",&St.x,&St.y,&Fn.x,&Fn.y);

scanf("%d",&p);

bool flag=1;

while(p--)

{

scanf("%d%d%d%d",&x1,&x2,&y1,&y2);

for(int i=x1;i<=x2;i++)

{

for(int j=y1;j<=y2;j++)

{

//gr2D[i][j]=1;

for(int k=0;k<7;k++)

{

for(int l=0;l<7;l++)

{

gr[i][j][k][l]=1;

if(i==Fn.x && j==Fn.y)

flag=0;

}

if(St.x==Fn.x && St.y==Fn.y)

printf("Optimal solution takes 0 hops.\n");

else

{

if(flag==0)

printf("No solution.\n");

else

bfs();

}

return 0;

}

10067

Asif NaeemMay 26, 2015

#include <iostream>
#include <queue>

using namespace std;

bool visit[10][10][10][10];

int arr[3]={0,1,-1};

struct states{
	int a,b,c,d;
	int step;
	};

int main()
{
	int t,n,stp;
	states tmp;
	int tw,tx,ty,tz;
	int a,b,c,d,x,y,w,z;
	cin>>t;
	while(t--)
	{
		states src,trgt,tmp;

		for(int i=0;i<10;i++)
			for(int j=0;j<10;j++)
				for(int k=0;k<10;k++)
					for(int l=0;l<10;l++)
						visit[i][j][k][l]=0;
		cin>>a>>b>>c>>d;
		src.a=a; src.b=b;
		src.c=c; src.d=d;
		src.step=0;

		cin>>a>>b>>c>>d;
		trgt.a=a; trgt.b=b;
		trgt.c=c; trgt.d=d;
		trgt.step=-1;

		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>a>>b>>c>>d;
			visit[a][b][c][d]=1;
		}

		queue<states> q;
		q.push(src);
		while(!q.empty())
		{
			tmp = q.front();q.pop();
			w=tmp.a;
			x=tmp.b;
			y=tmp.c;
			z=tmp.d;
			stp=tmp.step;
			visit[w][x][y][z]=1;

			if(w==trgt.a && x==trgt.b && y==trgt.c && z==trgt.d)
			{
				trgt.step=stp;
				break;
			}

			int tarr[4]={w,x,y,z};
			for(int i=0;i<4;i++)
			{
				int xx=tarr[i];
				tarr[i]=(tarr[i]+1)%10;
				if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)
				{
					tmp.a=tarr[0]; tmp.b=tarr[1];
					tmp.c=tarr[2]; tmp.d=tarr[3];
					tmp.step=stp+1;
					visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;
					q.push(tmp);
				}
				tarr[i]=xx;
				tarr[i]=((xx-1)<0?9:(xx-1)%10);
				if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)
				{
					tmp.a=tarr[0]; tmp.b=tarr[1];
					tmp.c=tarr[2]; tmp.d=tarr[3];
					tmp.step=stp+1;
					visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;
					q.push(tmp);
				}
				tarr[i]=xx;
			}
			//cout<<"sdjj\n";
		}
		if(trgt.step!=-1)
		cout<<trgt.step<<"\n";
		else
		cout<<-1<<"\n";
	}

	return 0;
}

100

101

#include <iostream>

#include <queue>

using namespace std;

bool visit[10][10][10][10];

int arr[3]={0,1,-1};

struct states{

int a,b,c,d;

int step;

};

int main()

{

int t,n,stp;

states tmp;

int tw,tx,ty,tz;

int a,b,c,d,x,y,w,z;

cin>>t;

while(t--)

{

states src,trgt,tmp;

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

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

for(int k=0;k<10;k++)

for(int l=0;l<10;l++)

visit[i][j][k][l]=0;

cin>>a>>b>>c>>d;

src.a=a; src.b=b;

src.c=c; src.d=d;

src.step=0;

cin>>a>>b>>c>>d;

trgt.a=a; trgt.b=b;

trgt.c=c; trgt.d=d;

trgt.step=-1;

cin>>n;

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

{

cin>>a>>b>>c>>d;

visit[a][b][c][d]=1;

}

queue<states> q;

q.push(src);

while(!q.empty())

{

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

w=tmp.a;

x=tmp.b;

y=tmp.c;

z=tmp.d;

stp=tmp.step;

visit[w][x][y][z]=1;

if(w==trgt.a && x==trgt.b && y==trgt.c && z==trgt.d)

{

trgt.step=stp;

break;

}

int tarr[4]={w,x,y,z};

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

{

int xx=tarr[i];

tarr[i]=(tarr[i]+1)%10;

if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)

{

tmp.a=tarr[0]; tmp.b=tarr[1];

tmp.c=tarr[2]; tmp.d=tarr[3];

tmp.step=stp+1;

visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;

q.push(tmp);

}

tarr[i]=xx;

tarr[i]=((xx-1)<0?9:(xx-1)%10);

if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0)

{

tmp.a=tarr[0]; tmp.b=tarr[1];

tmp.c=tarr[2]; tmp.d=tarr[3];

tmp.step=stp+1;

visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1;

q.push(tmp);

}

tarr[i]=xx;

}

//cout<<"sdjj\n";

}

if(trgt.step!=-1)

cout<<trgt.step<<"\n";

else

cout<<-1<<"\n";

}

return 0;

}

Category: DFS AND BFS

10336

521

794

710

633

627

321

314

298

10067

Archives

Categories