Graph Algorithm – Page 2 – Live with passion

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;

}

1208

Asif NaeemAugust 23, 2015

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

using namespace std;

struct Edge{
	int source,destination,weight;
};
//to keep track of parent and rank of union find
struct subset{
	int parent;
	int rank;
};
bool graph[100][100];
vector<Edge> edges;
subset* subsets;

bool cmp(Edge a,Edge b)
{
	return a.weight<b.weight;
}

int find(int node)
{
	if(subsets[node].parent!=node)
		return find(subsets[node].parent);
	return subsets[node].parent;
}

void Union(int x,int y)
{
	int xroot = find(x);
	int yroot = find(y);

	if(subsets[xroot].rank<subsets[yroot].rank)
		subsets[xroot].parent=yroot;
	else if(subsets[yroot].rank<subsets[xroot].rank)
		subsets[yroot].parent=xroot;
	else
	{
		subsets[yroot].parent=xroot;
		subsets[xroot].rank+=1;
	}

}
int main()
{
	int t,no_Of_Vertices,a;
	int counter,kase=1;
	stringstream ss;
	string s;
	Edge tEdge;
	Edge result[100];

	cin>>t;
	getchar();
	while(t--)
	{
		cin>>no_Of_Vertices;
		getchar();
		subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices);
		memset(graph,0,sizeof(graph));
		edges.clear();
		counter=0;
		for(int I=0;I<no_Of_Vertices;I++)
		{
			getline(cin,s);
			ss.clear();
			ss<<s;
			for(int K=0;K<no_Of_Vertices;K++)
			{
				ss>>a;
				if(ss.peek()==',')
					ss.ignore();
				if(a)
				{
					if(graph[I][K]==0)
					{
						graph[I][K]=graph[K][I]=1;
						tEdge.source=I;
						tEdge.destination=K;
						tEdge.weight=a;
						edges.push_back(tEdge);
					}
				}
			}
		}

		sort(edges.begin(),edges.end(),cmp);
		for(int I=0;I<no_Of_Vertices;I++)
		{
			subsets[I].parent=I;
			subsets[I].rank=0;
		}
		int i=0;
		while(counter<no_Of_Vertices-1)
		{
			tEdge = edges[i++];

			int x = find(tEdge.source);
			int y = find(tEdge.destination);

			if(x!=y)
			{
				result[counter++]=tEdge;
				Union(x,y);
			}
		}
		cout<<"Case "<<kase++<<":\n";
		char ch='A';
		for(int i=0;i<counter;i++)
		cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\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

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <string>

#include <sstream>

#include <algorithm>

using namespace std;

struct Edge{

int source,destination,weight;

};

//to keep track of parent and rank of union find

struct subset{

int parent;

int rank;

};

bool graph[100][100];

vector<Edge> edges;

subset* subsets;

bool cmp(Edge a,Edge b)

{

return a.weight<b.weight;

}

int find(int node)

{

if(subsets[node].parent!=node)

return find(subsets[node].parent);

return subsets[node].parent;

}

void Union(int x,int y)

{

int xroot = find(x);

int yroot = find(y);

if(subsets[xroot].rank<subsets[yroot].rank)

subsets[xroot].parent=yroot;

else if(subsets[yroot].rank<subsets[xroot].rank)

subsets[yroot].parent=xroot;

else

{

subsets[yroot].parent=xroot;

subsets[xroot].rank+=1;

}

int main()

{

int t,no_Of_Vertices,a;

int counter,kase=1;

stringstream ss;

string s;

Edge tEdge;

Edge result[100];

cin>>t;

getchar();

while(t--)

{

cin>>no_Of_Vertices;

getchar();

subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices);

memset(graph,0,sizeof(graph));

edges.clear();

counter=0;

for(int I=0;I<no_Of_Vertices;I++)

{

getline(cin,s);

ss.clear();

ss<<s;

for(int K=0;K<no_Of_Vertices;K++)

{

ss>>a;

if(ss.peek()==',')

ss.ignore();

if(a)

{

if(graph[I][K]==0)

{

graph[I][K]=graph[K][I]=1;

tEdge.source=I;

tEdge.destination=K;

tEdge.weight=a;

edges.push_back(tEdge);

}

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

for(int I=0;I<no_Of_Vertices;I++)

{

subsets[I].parent=I;

subsets[I].rank=0;

}

int i=0;

while(counter<no_Of_Vertices-1)

{

tEdge = edges[i++];

int x = find(tEdge.source);

int y = find(tEdge.destination);

if(x!=y)

{

result[counter++]=tEdge;

Union(x,y);

}

cout<<"Case "<<kase++<<":\n";

char ch='A';

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

cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\n";

}

return 0;

}

10048

Asif NaeemJuly 8, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define INF 1000000
using namespace std;

int gr[105][105];

int _mn(int a,int b)
{
	if(a>b)
	return b;
	return a;
}

int _mx(int a,int b)
{
	if(a>b)
	return a;
	return b;
}
int main()
{
	bool f=0;
	int kase=1;
	int C,S,Q;
	int a,b,d;

	while(cin>>C)
	{
		cin>>S>>Q;

		if(C+S+Q==0)
		break;

		for(int i=1;i<105;i++)
		{
			for(int j=1;j<105;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				gr[i][j]=INF;
			}
		}
		for(int i=1;i<=S;i++)
		{
			cin>>a>>b>>d;
			gr[a][b]=d;
			gr[b][a]=d;
		}

		for(int i=1;i<=C;i++)
		{
			for(int j=1;j<=C;j++)
			{
				for(int k=1;k<=C;k++)
				{
					gr[j][k]=_mn(gr[j][k],_mx(gr[j][i],gr[i][k]));
				}
			}
		}

		if(f)
		cout<<"\n";
		f=1;
		cout<<"Case #"<<kase++<<"\n";
		for(int i=0;i<Q;i++)
		{
			cin>>a>>b;
			if(gr[a][b]==INF)
			cout<<"no path\n";
			else
			cout<<gr[a][b]<<"\n";
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#define INF 1000000

using namespace std;

int gr[105][105];

int _mn(int a,int b)

{

if(a>b)

return b;

return a;

}

int _mx(int a,int b)

{

if(a>b)

return a;

return b;

}

int main()

{

bool f=0;

int kase=1;

int C,S,Q;

int a,b,d;

while(cin>>C)

{

cin>>S>>Q;

if(C+S+Q==0)

break;

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

{

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

{

if(i==j)

gr[i][j]=0;

else

gr[i][j]=INF;

}

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

{

cin>>a>>b>>d;

gr[a][b]=d;

gr[b][a]=d;

}

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

{

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

{

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

{

gr[j][k]=_mn(gr[j][k],_mx(gr[j][i],gr[i][k]));

}

if(f)

cout<<"\n";

f=1;

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

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

{

cin>>a>>b;

if(gr[a][b]==INF)

cout<<"no path\n";

else

cout<<gr[a][b]<<"\n";

}

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;

}

10047

Asif NaeemMay 25, 2015

#include <iostream>
#include <queue>

#define Green 0
#define Black 1
#define Red 2
#define Blue 3
#define White 4

#define N 0
#define W 1
#define S 2
#define E 3

using namespace std;

struct states{
	int ro,col,wt,direction,wheelcolr;
	};

int m,n,ans;


bool bfs(states src,states trgt,char gr[30][30])
{
	int r,c,d,colr,weight;
	states tmp;
	queue<states> q;
	q.push(src);
	bool visit[30][30][4][5];//r,c,dir,col
	for(int i=0;i<30;i++)
		for(int j=0;j<30;j++)
			for(int k=0;k<4;k++)
				for(int l=0;l<5;l++)
					visit[i][j][k][l]=0;

	while(!q.empty())
	{
		tmp=q.front();q.pop();
		r=tmp.ro; c=tmp.col; d=tmp.direction; colr=tmp.wheelcolr;
		weight=tmp.wt;
		visit[r][c][d][colr]=true;

		if(r==trgt.ro && c==trgt.col && colr==Green)
		{
			trgt.wt=weight;
			ans=weight;
			return 1;
		}
		if(d==N)
		{
			if(!visit[r][c][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r-1>=0 && !visit[r-1][c][N][(colr+1)%5] && gr[r-1][c]!='#')
			{
				tmp.ro=r-1; tmp.col=c; tmp.direction=N; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==S)
		{
			if(!visit[r][c][E][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][W][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(r+1<m && !visit[r+1][c][S][(colr+1)%5] && gr[r+1][c]!='#')
			{
				tmp.ro=r+1; tmp.col=c; tmp.direction=S; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==W)
		{
			if(!visit[r][c][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c-1>=0 && !visit[r][c-1][W][(colr+1)%5] && gr[r][c-1]!='#')
			{
				tmp.ro=r; tmp.col=c-1; tmp.direction=W; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}
		else if(d==E)
		{
			if(!visit[r][c][N][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(!visit[r][c][S][colr])
			{
				tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;
				tmp.wt=weight+1;
				q.push(tmp);
			}
			if(c+1<n && !visit[r][c+1][E][(colr+1)%5] && gr[r][c+1]!='#')
			{
				tmp.ro=r; tmp.col=c+1; tmp.direction=E; tmp.wheelcolr=(colr+1)%5;
				tmp.wt=weight+1;
				q.push(tmp);
			}
		}

	}
	return 0;
}
int main()
{
	int kase=1;
	while(cin>>m)
	{
		cin>>n;
		if(m+n==0)
		break;
		states src,trgt;
		char gr[30][30];
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>gr[i][j];
				if(gr[i][j]=='S')
				{
					src.ro=i;src.col=j;src.wt=0;
					src.direction=N;src.wheelcolr=Green;
				}
				if(gr[i][j]=='T')
				{
					trgt.ro=i;trgt.col=j;trgt.wt=0;
					trgt.direction=0;trgt.wheelcolr=Green;
				}
			}
		}

		if(kase>1)
			cout<<"\nCase #"<<kase++<<"\n";
		else
			cout<<"Case #"<<kase++<<"\n";
		if(!bfs(src,trgt,gr))
		{
			cout<<"destination not reachable\n";
		}
		else
		{
			cout<<"minimum time = "<<ans<<" sec\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

#include <iostream>

#include <queue>

#define Green 0

#define Black 1

#define Red 2

#define Blue 3

#define White 4

#define N 0

#define W 1

#define S 2

#define E 3

using namespace std;

struct states{

int ro,col,wt,direction,wheelcolr;

};

int m,n,ans;

bool bfs(states src,states trgt,char gr[30][30])

{

int r,c,d,colr,weight;

states tmp;

queue<states> q;

q.push(src);

bool visit[30][30][4][5];//r,c,dir,col

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

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

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

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

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

while(!q.empty())

{

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

r=tmp.ro; c=tmp.col; d=tmp.direction; colr=tmp.wheelcolr;

weight=tmp.wt;

visit[r][c][d][colr]=true;

if(r==trgt.ro && c==trgt.col && colr==Green)

{

trgt.wt=weight;

ans=weight;

return 1;

}

if(d==N)

{

if(!visit[r][c][E][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][W][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(r-1>=0 && !visit[r-1][c][N][(colr+1)%5] && gr[r-1][c]!='#')

{

tmp.ro=r-1; tmp.col=c; tmp.direction=N; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==S)

{

if(!visit[r][c][E][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=E; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][W][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=W; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(r+1<m && !visit[r+1][c][S][(colr+1)%5] && gr[r+1][c]!='#')

{

tmp.ro=r+1; tmp.col=c; tmp.direction=S; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==W)

{

if(!visit[r][c][N][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][S][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(c-1>=0 && !visit[r][c-1][W][(colr+1)%5] && gr[r][c-1]!='#')

{

tmp.ro=r; tmp.col=c-1; tmp.direction=W; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

else if(d==E)

{

if(!visit[r][c][N][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=N; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(!visit[r][c][S][colr])

{

tmp.ro=r; tmp.col=c; tmp.direction=S; tmp.wheelcolr=colr;

tmp.wt=weight+1;

q.push(tmp);

}

if(c+1<n && !visit[r][c+1][E][(colr+1)%5] && gr[r][c+1]!='#')

{

tmp.ro=r; tmp.col=c+1; tmp.direction=E; tmp.wheelcolr=(colr+1)%5;

tmp.wt=weight+1;

q.push(tmp);

}

return 0;

}

int main()

{

int kase=1;

while(cin>>m)

{

cin>>n;

if(m+n==0)

break;

states src,trgt;

char gr[30][30];

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

{

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

{

cin>>gr[i][j];

if(gr[i][j]=='S')

{

src.ro=i;src.col=j;src.wt=0;

src.direction=N;src.wheelcolr=Green;

}

if(gr[i][j]=='T')

{

trgt.ro=i;trgt.col=j;trgt.wt=0;

trgt.direction=0;trgt.wheelcolr=Green;

}

if(kase>1)

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

else

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

if(!bfs(src,trgt,gr))

{

cout<<"destination not reachable\n";

}

else

{

cout<<"minimum time = "<<ans<<" sec\n";

}

return 0;

}

10199

Asif NaeemApril 28, 2015

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>

using namespace std;

map<string,int> mp;
map<int,string> mp2;
vector<int> gr[105];
//vector<int> V;
bool visit[105];
bool ap[105];
int discTime[105];
int low[105];
int par[105];
int cnt;
set<string> SET;
void cutvertex(int u)
{
	static int dsc_time=0;
	low[u]=discTime[u]=dsc_time++;
	visit[u]=1;
	int child=0;
	for(int i=0;i<gr[u].size();i++)
	{
		int v = gr[u][i];
		if(visit[v]==0)
		{
			par[v]=u;
			child++;
			cutvertex(v);
			low[u]=min(low[u],low[v]);

			if(par[u]==-1 && child>1)
			{
				if(ap[u]==0)
				{
					ap[u]=1;
					SET.insert(mp2[u]);
					cnt++;
				}
			}
			else if(low[v]>=discTime[u] && par[u]!=-1)
			{
				if(ap[u]==0)
				{
					ap[u]=1;
					SET.insert(mp2[u]);
					cnt++;
				}
			}
		}
		else if(v!=par[u])
		{
			low[u]=min(low[u],discTime[v]);
		}
	}
}

int main()
{
	string s,s2;
	int N,R;
	int kase=1;
	bool flag=0;
	while(scanf("%d",&N),N)
	{
		mp.clear();
		mp2.clear();
		cnt=0;
		for(int i=0;i<105;i++)
		{
			gr[i].clear();
			visit[i]=0;
			ap[i]=0;
			par[i]=-1;
			discTime[i]=0;
			low[i]=0;
		}
		for(int i=1;i<=N;i++)
		{
			cin>>s;
			mp2[i]=s;
			mp[s]=i;
		}
		cin>>R;
		for(int i=1;i<=R;i++)
		{
			cin>>s>>s2;
			gr[mp[s]].push_back(mp[s2]);
			gr[mp[s2]].push_back(mp[s]);
		}
		SET.clear();
		for(int i=1;i<=N;i++)
		{
			if(visit[i]==0)
				cutvertex(i);
		}
		if(flag)
		cout<<"\n";
		flag=1;
		cout<<"City map #"<<kase++<<": "<<cnt<<" camera(s) found\n";
		for(set<string>::iterator it=SET.begin();it!=SET.end();++it)
		{
			cout<<*it<<"\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <iostream>

#include <cstdio>

#include <vector>

#include <sstream>

#include <string>

#include <algorithm>

#include <queue>

#include <cstring>

#include <map>

#include <set>

using namespace std;

map<string,int> mp;

map<int,string> mp2;

vector<int> gr[105];

//vector<int> V;

bool visit[105];

bool ap[105];

int discTime[105];

int low[105];

int par[105];

int cnt;

set<string> SET;

void cutvertex(int u)

{

static int dsc_time=0;

low[u]=discTime[u]=dsc_time++;

visit[u]=1;

int child=0;

for(int i=0;i<gr[u].size();i++)

{

int v = gr[u][i];

if(visit[v]==0)

{

par[v]=u;

child++;

cutvertex(v);

low[u]=min(low[u],low[v]);

if(par[u]==-1 && child>1)

{

if(ap[u]==0)

{

ap[u]=1;

SET.insert(mp2[u]);

cnt++;

}

else if(low[v]>=discTime[u] && par[u]!=-1)

{

if(ap[u]==0)

{

ap[u]=1;

SET.insert(mp2[u]);

cnt++;

}

else if(v!=par[u])

{

low[u]=min(low[u],discTime[v]);

}

int main()

{

string s,s2;

int N,R;

int kase=1;

bool flag=0;

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

{

mp.clear();

mp2.clear();

cnt=0;

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

{

gr[i].clear();

visit[i]=0;

ap[i]=0;

par[i]=-1;

discTime[i]=0;

low[i]=0;

}

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

{

cin>>s;

mp2[i]=s;

mp[s]=i;

}

cin>>R;

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

{

cin>>s>>s2;

gr[mp[s]].push_back(mp[s2]);

gr[mp[s2]].push_back(mp[s]);

}

SET.clear();

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

{

if(visit[i]==0)

cutvertex(i);

}

if(flag)

cout<<"\n";

flag=1;

cout<<"City map #"<<kase++<<": "<<cnt<<" camera(s) found\n";

for(set<string>::iterator it=SET.begin();it!=SET.end();++it)

{

cout<<*it<<"\n";

}

return 0;

}

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks. For

Continue Reading “315” →

872

Asif NaeemMarch 22, 2015

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

int noOfelement;
int mp[26];
string str,str1,str2;
string output[2000];
int kk;
bool gr[27][27];
stringstream ss;
int elements[26];
set<string> SET;
//ofstream out;

bool check(int elemnt,bool visit[])
{
	for(int i=0;i<26;i++)
	{
		if(gr[i][elemnt] && mp[i]!=-1 && visit[mp[i]]==0)
		return 0;
	}
	return 1;
}

int recur(bool used[],string s)
{
	if(s.size()==noOfelement)
	{
		output[kk++]=s;
		return 0;
	}

	for(int i=0;i<noOfelement;i++)
	{
		if(used[i]==0 && check(elements[i],used)==1)
		{
			used[i]=1;
			s.append(1u,char(elements[i]+'A'));
			recur(used,s);
			s.erase(s.begin()+(s.size()-1));
			used[i]=0;
		}
	}
	return 0;
}

void topologicalsort()
{
	bool visit[noOfelement];
	string res = "";
	for(int i=0;i<noOfelement;i++)
	{
		visit[i]=false;
	}
	for(int i=0;i<noOfelement;i++)
	{
		if(visit[i]==0 && check(elements[i],visit)==1)
		{
			visit[i]=1;
			res.append(1u,char(elements[i]+'A'));
			recur(visit,res);
			res.erase(res.begin()+(res.size()-1));
			visit[i]=0;
		}
	}

}

bool cmp(string s1,string s2)
{
	int sum = 0;
	for(int i=0;i<s1.size();i++)
	{
		if(s1[i]!=s2[i])
		{
			return (s1[i]<s2[i]);
		}
	}
}
int main()
{
	int cnt = 0,t;
	int a,b;
	stringstream ss;
	bool first = 0;
	char c;

	getline(cin,str);
	ss<<str;
	ss>>t;
	ss.clear();
	getline(cin,str);

	while(t--)
	{
		getline(cin,str1);
		getline(cin,str2);
		if(t)
		getline(cin,str);

		ss.clear();
		ss<<str1;
		for(int i=0;i<26;i++)
		{
			mp[i]=-1;
			elements[i]=0;
			for(int j=0;j<26;j++)
			gr[i][j]=0;
		}
		noOfelement=0;
		while(ss>>c)
		{
			mp[c-'A']=noOfelement;
			elements[noOfelement]=c-'A';
			noOfelement++;
		}

		ss.clear();
		ss<<str2;
		bool f = 0;
		char tmp[200];
		int char_cnt = 0;
		while(ss>>c)
		{
			if(c>='A' && c<='Z')
			tmp[char_cnt++]=c;
		}
		for(int i=0;i<char_cnt;i++)
		{
			if(i%2)
			{
				b = tmp[i]-'A';
				gr[a][b]=1;
			}
			else
			a = tmp[i]-'A';
		}
		kk=0;
		topologicalsort();
		sort(output+0,output+kk,cmp);
		for(int ii=0;ii<kk;ii++)
		{
			for(int jj=0;jj<output[ii].size();jj++)
			cout<<output[ii][jj]<<(jj!=output[ii].size()-1?" ":"\n");
		}
		if(kk==0)
		cout<<"NO\n";
		if(t)
		cout<<"\n";
	}

	//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

#include <iostream>

#include <string>

#include <sstream>

#include <fstream>

#include <queue>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;

int noOfelement;

int mp[26];

string str,str1,str2;

string output[2000];

int kk;

bool gr[27][27];

stringstream ss;

int elements[26];

set<string> SET;

//ofstream out;

bool check(int elemnt,bool visit[])

{

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

{

if(gr[i][elemnt] && mp[i]!=-1 && visit[mp[i]]==0)

return 0;

}

return 1;

}

int recur(bool used[],string s)

{

if(s.size()==noOfelement)

{

output[kk++]=s;

return 0;

}

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

{

if(used[i]==0 && check(elements[i],used)==1)

{

used[i]=1;

s.append(1u,char(elements[i]+'A'));

recur(used,s);

s.erase(s.begin()+(s.size()-1));

used[i]=0;

}

return 0;

}

void topologicalsort()

{

bool visit[noOfelement];

string res = "";

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

{

visit[i]=false;

}

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

{

if(visit[i]==0 && check(elements[i],visit)==1)

{

visit[i]=1;

res.append(1u,char(elements[i]+'A'));

recur(visit,res);

res.erase(res.begin()+(res.size()-1));

visit[i]=0;

}

bool cmp(string s1,string s2)

{

int sum = 0;

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

{

if(s1[i]!=s2[i])

{

return (s1[i]<s2[i]);

}

int main()

{

int cnt = 0,t;

int a,b;

stringstream ss;

bool first = 0;

char c;

getline(cin,str);

ss<<str;

ss>>t;

ss.clear();

getline(cin,str);

while(t--)

{

getline(cin,str1);

getline(cin,str2);

if(t)

getline(cin,str);

ss.clear();

ss<<str1;

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

{

mp[i]=-1;

elements[i]=0;

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

gr[i][j]=0;

}

noOfelement=0;

while(ss>>c)

{

mp[c-'A']=noOfelement;

elements[noOfelement]=c-'A';

noOfelement++;

}

ss.clear();

ss<<str2;

bool f = 0;

char tmp[200];

int char_cnt = 0;

while(ss>>c)

{

if(c>='A' && c<='Z')

tmp[char_cnt++]=c;

}

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

{

if(i%2)

{

b = tmp[i]-'A';

gr[a][b]=1;

}

else

a = tmp[i]-'A';

}

kk=0;

topologicalsort();

sort(output+0,output+kk,cmp);

for(int ii=0;ii<kk;ii++)

{

for(int jj=0;jj<output[ii].size();jj++)

cout<<output[ii][jj]<<(jj!=output[ii].size()-1?" ":"\n");

}

if(kk==0)

cout<<"NO\n";

if(t)

cout<<"\n";

}

//out.close();

return 0;

}

Category: Graph Algorithm

321

314

298

1208

10048

10067

10047

10199

315

872

Archives

Categories