Graph Algorithm – Page 3 – Live with passion

124

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;
		//cout<<s<<"\n";
		//out<<s<<"\n";
		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;
	int a,b;
	bool first = 0;
	char c;

	while(getline(cin,str))
	{
		cnt+=1;
		if(cnt%2)
		{
			str1 = 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++;
			}
		}
		else
		{
			str2=str;
			ss.clear();
			ss<<str2;
			bool f = 0;
			while(ss>>c)
			{
				if(f)
				{
					b = c -'a';gr[a][b]=1;
				}
				else
				a = c-'a';
				f = !f;
			}
			kk=0;
			topologicalsort();
			if (first) cout<<"\n";
		    first = 1;
			sort(output+0,output+kk,cmp);
			for(int ii=0;ii<kk;ii++)
			{
				cout<<output[ii]<<"\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

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

//cout<<s<<"\n";

//out<<s<<"\n";

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;

int a,b;

bool first = 0;

char c;

while(getline(cin,str))

{

cnt+=1;

if(cnt%2)

{

str1 = 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++;

}

else

{

str2=str;

ss.clear();

ss<<str2;

bool f = 0;

while(ss>>c)

{

if(f)

{

b = c -'a';gr[a][b]=1;

}

else

a = c-'a';

f = !f;

}

kk=0;

topologicalsort();

if (first) cout<<"\n";

first = 1;

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

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

{

cout<<output[ii]<<"\n";

}

//out.close();

return 0;

}

452

Asif NaeemMarch 21, 2015

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

#define INF 10000000

using namespace std;

bool gr[26][26];
int daysreq[26],indegree[26];
int accumulated_days[26];
int t;

int bfs(queue<int> q)
{

	while(!q.empty())
	{
		int a = q.front();q.pop();
		for(int i=0;i<26;i++)
		{
			if(gr[a][i])
			{
				accumulated_days[i]=max(accumulated_days[i],accumulated_days[a]+daysreq[i]);
				if(--indegree[i]==0)
				q.push(i);
			}

		}

	}

	int MX = 0;
	for(int i=0;i<26;i++)
	{
		MX =  max(accumulated_days[i],MX);
	}
	cout<<MX<<"\n";
	if(t)
	cout<<"\n";

	return 0;
}

int main()
{
	string s;
	stringstream ss;
	getline(cin,s);
	ss<<s;
	ss>>t;
	getline(cin,s);
	ss.clear();
	while(t--)
	{
		for(int i=0;i<26;i++)
		{
			daysreq[i]=0;
			indegree[i]=0;
			accumulated_days[i]=0;
			for(int j=0;j<26;j++)
				gr[i][j]=0;
		}
		while(getline(cin,s) && s!="")
		{
			ss<<s;
			char c;
			int d,u;
			ss>>c>>d;
			u = c-'A';
			daysreq[u]=d;
			while(ss>>c)
			{
				gr[c-'A'][u]=1;
			}
			ss.clear();
		}

		for(int i=0;i<26;i++)
		{
			for(int j=0;j<26;j++)
			{
				if(gr[i][j])
					indegree[j]++;
			}
		}
		queue<int> q;
		for(int i=0;i<26;i++)
		{
			if(daysreq[i]!=0 && indegree[i]==0)
			{
				accumulated_days[i]=daysreq[i];
				q.push(i);
			}
		}
		bfs(q);
	}
	return 0;
}

100

101

#include <iostream>

#include <sstream>

#include <string>

#include <queue>

#include <cstdio>

#define INF 10000000

using namespace std;

bool gr[26][26];

int daysreq[26],indegree[26];

int accumulated_days[26];

int t;

int bfs(queue<int> q)

{

while(!q.empty())

{

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

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

{

if(gr[a][i])

{

accumulated_days[i]=max(accumulated_days[i],accumulated_days[a]+daysreq[i]);

if(--indegree[i]==0)

q.push(i);

}

int MX = 0;

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

{

MX = max(accumulated_days[i],MX);

}

cout<<MX<<"\n";

if(t)

cout<<"\n";

return 0;

}

int main()

{

string s;

stringstream ss;

getline(cin,s);

ss<<s;

ss>>t;

getline(cin,s);

ss.clear();

while(t--)

{

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

{

daysreq[i]=0;

indegree[i]=0;

accumulated_days[i]=0;

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

gr[i][j]=0;

}

while(getline(cin,s) && s!="")

{

ss<<s;

char c;

int d,u;

ss>>c>>d;

u = c-'A';

daysreq[u]=d;

while(ss>>c)

{

gr[c-'A'][u]=1;

}

ss.clear();

}

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

{

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

{

if(gr[i][j])

indegree[j]++;

}

queue<int> q;

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

{

if(daysreq[i]!=0 && indegree[i]==0)

{

accumulated_days[i]=daysreq[i];

q.push(i);

}

bfs(q);

}

return 0;

}

10937

Asif NaeemMarch 19, 2015

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

#define INF 10000
using namespace std;

int location,target;
vector<vector<int> > dp;
int h,w;
int graph[200][200];
string str[60];

struct POINT{
	int x,y;
};

POINT pp[3030];
POINT src,tr;
int k;
int dirx[4]={1,0,0,-1};
int diry[4]={0,1,-1,0};

int bfs(int s,int t)
{
	int tmpy,tmpx;
	queue<int> q;
	bool visit[55][55];
	int dist[55][55];

	memset(dist,0,sizeof(dist));
	for(int i=0;i<55;i++)
	{
		for(int j=0;j<55;j++)
		{
			dist[i][j]=INF;
			visit[i][j]=false;
		}
	}

	tmpx = pp[s].x;
	tmpy = pp[s].y;

	q.push(tmpx);
	q.push(tmpy);

	visit[tmpx][tmpy]=1;
	dist[tmpx][tmpy]=0;

	while(!q.empty())
	{
		int a = q.front();q.pop();
		int b = q.front();q.pop();

		for(int i=0;i<4;i++)
		{
			int tx = a+dirx[i];
			int ty = b+diry[i];
			if(tx<0 || tx>=h)
			continue;
			if(ty<0 || ty>=w)
			continue;
			if(str[tx][ty]=='#')
			continue;

			if(!visit[tx][ty])
			{
				q.push(tx);q.push(ty);
				visit[tx][ty]=1;
				dist[tx][ty]=dist[a][b]+1;
			}
		}
	}

	return dist[pp[t].x][pp[t].y];
}

int tsp(int status,int location)
{
	if(dp[status][location]!=-1)
	return dp[status][location];

	dp[status][location] = 1e9;

	int mask = 1<<location;

	for(int i=0;i<k;i++)
	{
		if(i!=location && (status & (1<<i)))
		dp[status][location]= min(dp[status][location],tsp(status-mask,i)+graph[i][location]);
	}
	return dp[status][location];
}

int main()
{
	int dx[8]={1,0,0,-1,1,1,-1,-1};
	int dy[8]={0,1,-1,0,1,-1,-1,1};

	while(cin>>h)
	{
		cin>>w;
		if(h+w==0)
		break;

		for(int i=0;i<h;i++)
			cin>>str[i];
		memset(graph,0,sizeof(graph));

		int res = 0;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='~')
				{
					str[i][j]='#';
				}
				else if(str[i][j]=='*')
				{
					str[i][j]='#';
					for(int l=0;l<8;l++)
					{
						if(i+dx[l]<0 || i+dx[l]>=h)
						continue;
						if(j+dy[l]<0 || j+dy[l]>=w)
						continue;
						if(str[i+dx[l]][j+dy[l]]=='!' || str[i+dx[l]][j+dy[l]]=='@')
						res = -1;
						if(str[i+dx[l]][j+dy[l]]!='*')
							str[i+dx[l]][j+dy[l]]='#';
					}
				}
			}
		}

		if(res==-1)
		{
			cout<<-1<<"\n";
			continue;
		}
		k = 0;
		location = -1; target = -1;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='!')
				{
					pp[k].x = i; pp[k].y = j; k+=1;
				}
				else if(str[i][j]=='@')
				{
					location = k;
					pp[k].x = i; pp[k].y = j; k+=1;
				}
			}
		}

		if(k==1)
		{
			cout<<0<<"\n";
			continue;
		}
		for(int i=0;i<k;i++)
		{
			for(int j=i+1;j<k;j++)
			{
					graph[i][j]=bfs(i,j);
					graph[j][i] = graph[i][j];
			}
		}

		dp = vector< vector< int > >(1<<k,vector<int>(k,-1));
		for(int i=0;i<k;i++)
			dp[1<<i][i]=graph[location][i];

		res = tsp((1<<(k))-1,location);
		if(res>=INF)
		{
			cout<<-1<<"\n";
			continue;
		}
		cout<<res<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

#include <cstdio>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <string>

#define INF 10000

using namespace std;

int location,target;

vector<vector<int> > dp;

int h,w;

int graph[200][200];

string str[60];

struct POINT{

int x,y;

};

POINT pp[3030];

POINT src,tr;

int k;

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

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

int bfs(int s,int t)

{

int tmpy,tmpx;

queue<int> q;

bool visit[55][55];

int dist[55][55];

memset(dist,0,sizeof(dist));

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

{

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

{

dist[i][j]=INF;

visit[i][j]=false;

}

tmpx = pp[s].x;

tmpy = pp[s].y;

q.push(tmpx);

q.push(tmpy);

visit[tmpx][tmpy]=1;

dist[tmpx][tmpy]=0;

while(!q.empty())

{

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

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

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

{

int tx = a+dirx[i];

int ty = b+diry[i];

if(tx<0 || tx>=h)

continue;

if(ty<0 || ty>=w)

continue;

if(str[tx][ty]=='#')

continue;

if(!visit[tx][ty])

{

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

visit[tx][ty]=1;

dist[tx][ty]=dist[a][b]+1;

}

return dist[pp[t].x][pp[t].y];

}

int tsp(int status,int location)

{

if(dp[status][location]!=-1)

return dp[status][location];

dp[status][location] = 1e9;

int mask = 1<<location;

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

{

if(i!=location && (status & (1<<i)))

dp[status][location]= min(dp[status][location],tsp(status-mask,i)+graph[i][location]);

}

return dp[status][location];

}

int main()

{

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

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

while(cin>>h)

{

cin>>w;

if(h+w==0)

break;

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

cin>>str[i];

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

int res = 0;

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

{

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

{

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

{

str[i][j]='#';

}

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

{

str[i][j]='#';

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

{

if(i+dx[l]<0 || i+dx[l]>=h)

continue;

if(j+dy[l]<0 || j+dy[l]>=w)

continue;

if(str[i+dx[l]][j+dy[l]]=='!' || str[i+dx[l]][j+dy[l]]=='@')

res = -1;

if(str[i+dx[l]][j+dy[l]]!='*')

str[i+dx[l]][j+dy[l]]='#';

}

if(res==-1)

{

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

continue;

}

k = 0;

location = -1; target = -1;

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

{

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

{

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

{

pp[k].x = i; pp[k].y = j; k+=1;

}

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

{

location = k;

pp[k].x = i; pp[k].y = j; k+=1;

}

if(k==1)

{

cout<<0<<"\n";

continue;

}

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

{

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

{

graph[i][j]=bfs(i,j);

graph[j][i] = graph[i][j];

}

dp = vector< vector< int > >(1<<k,vector<int>(k,-1));

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

dp[1<<i][i]=graph[location][i];

res = tsp((1<<(k))-1,location);

if(res>=INF)

{

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

continue;

}

cout<<res<<"\n";

}

return 0;

}

10349

Asif NaeemMarch 17, 2015

This is a bipartite matching problem. This can be solved using Ford fulkerson algorithm for Max flow problem.

#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;

int gr[500][500];
int rgr[500][500];
string str[50];
int h,w;
int numOfantena;
int parent[500];
bool visited[500];
int src,targt;

bool bfs(int s, int t)
{
    memset(visited, 0, sizeof(visited));
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty())
    {
        int a = q.front();
        q.pop();

        for (int i=0; i<=targt; i++)
        {
            if (visited[i]==false && rgr[a][i] > 0)
            {
                q.push(i);
                parent[i] = a;
                visited[i] = true;
            }
        }
    }

    return (visited[t] == true);
}

int fordFulkerson(int s, int t)
{
    int u, v;

    for (u = 0; u <=targt; u++)
        for (v = 0; v <= targt; v++)
             rgr[u][v] = gr[u][v];


    int max_flow = 0;

	memset(parent, -1, sizeof(parent));
    while (bfs(s, t))
    {
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, rgr[u][v]);
        }

        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rgr[u][v] -= path_flow;
            rgr[v][u] += path_flow;
        }
        max_flow += path_flow;
    }

    return max_flow;
}


int main()
{
    int t;
	cin>>t;
	while(t--)
	{
		cin>>h>>w;
		numOfantena = 0;
		for(int i=0;i<h;i++)
		{
			cin>>str[i];
		}

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

		src = 0;
		targt = h*w+1;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='*')
				{
					numOfantena++;

					if((i+j)%2)
					{
						gr[src][i*w+j+1]=1;

						if(i-1>=0 && str[i-1][j]=='*')
						{
							gr[i*w+j+1][(i-1)*w+j+1]=1;
						}
						if(i+1<h && str[i+1][j]=='*')
						{
							gr[i*w+j+1][(i+1)*w+j+1]=1;
						}
						if(j-1>=0 && str[i][j-1]=='*')
						{
							gr[i*w+j+1][i*w+j-1+1]=1;
						}
						if(j+1<w && str[i][j+1]=='*')
						{
							gr[i*w+j+1][i*w+j+1+1]=1;
						}
					}
					else
						gr[i*w+j+1][targt]=1;
				}
			}
		}

		int flow = fordFulkerson(src, targt);
		cout<<(numOfantena-2*flow)+flow<<"\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

#include <iostream>

#include <limits.h>

#include <string.h>

#include <queue>

using namespace std;

int gr[500][500];

int rgr[500][500];

string str[50];

int h,w;

int numOfantena;

int parent[500];

bool visited[500];

int src,targt;

bool bfs(int s, int t)

{

memset(visited, 0, sizeof(visited));

queue <int> q;

q.push(s);

visited[s] = true;

parent[s] = -1;

while (!q.empty())

{

int a = q.front();

q.pop();

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

{

if (visited[i]==false && rgr[a][i] > 0)

{

q.push(i);

parent[i] = a;

visited[i] = true;

}

return (visited[t] == true);

}

int fordFulkerson(int s, int t)

{

int u, v;

for (u = 0; u <=targt; u++)

for (v = 0; v <= targt; v++)

rgr[u][v] = gr[u][v];

int max_flow = 0;

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

while (bfs(s, t))

{

int path_flow = INT_MAX;

for (v=t; v!=s; v=parent[v])

{

u = parent[v];

path_flow = min(path_flow, rgr[u][v]);

}

for (v=t; v != s; v=parent[v])

{

u = parent[v];

rgr[u][v] -= path_flow;

rgr[v][u] += path_flow;

}

max_flow += path_flow;

}

return max_flow;

}

int main()

{

int t;

cin>>t;

while(t--)

{

cin>>h>>w;

numOfantena = 0;

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

{

cin>>str[i];

}

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

memset(rgr,0,sizeof(rgr));

src = 0;

targt = h*w+1;

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

{

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

{

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

{

numOfantena++;

if((i+j)%2)

{

gr[src][i*w+j+1]=1;

if(i-1>=0 && str[i-1][j]=='*')

{

gr[i*w+j+1][(i-1)*w+j+1]=1;

}

if(i+1<h && str[i+1][j]=='*')

{

gr[i*w+j+1][(i+1)*w+j+1]=1;

}

if(j-1>=0 && str[i][j-1]=='*')

{

gr[i*w+j+1][i*w+j-1+1]=1;

}

if(j+1<w && str[i][j+1]=='*')

{

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

}

else

gr[i*w+j+1][targt]=1;

}

int flow = fordFulkerson(src, targt);

cout<<(numOfantena-2*flow)+flow<<"\n";

}

return 0;

}

10076

Asif NaeemMarch 8, 2015

Problem description error: ∆T = ⌈β2(h2 − h1)⌉ + γ, if h1 < h2 , here if we use γ as problem description,we get WA from online judge,so use δ here to get accepted.

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

#define INF 100000000

using namespace std;

int M,N;
int gr[20][20];
int dirx[4]={1,0,0,-1};
int diry[4]={0,1,-1,0};
float alpha1,alpha2;
int gema;
float beta1,beta2;
int delta;
int Rs,Cs,Rt,Ct;
int E;
int Time[20][20][205];
bool visit[20][20][205];
int MX;

struct State{
	int x,y,_energy,_time;
};


struct cmp{
	bool operator()(State one,State two)
	{
		return one._time<two._time;
	}
};

bool bfs()
{
	priority_queue<State,vector<State>,cmp> q;
	MX = INF;
	int valu,tt;

	for(int i=0;i<20;i++)
	{
		for(int j=0;j<20;j++)
		{
			for(int k=0;k<205;k++)
			{
				Time[i][j][k]=0;
				visit[i][j][k]=false;
			}
		}
	}

	visit[Rs][Cs][0]=1;
	State stat;
	stat.x = Rs;stat.y = Cs,stat._energy = 0; stat._time = 0;

	q.push(stat);
	int r,c,en,tm;
	Time[Rs][Cs][0]=0;
	bool Found=0;
	while(!q.empty())
	{
		State tstat = q.top();
		q.pop();

		r = tstat.x;//q.front();q.pop();
		c = tstat.y;//q.front();q.pop();
		en = tstat._energy;//q.front();q.pop();
		tm = tstat._time;
		if(r==Rt && c==Ct)
		{
			if(tm<MX)
			{
				MX = tm;//Time[r][c][en];
				Found = 1;
			}
			continue;
		}

		for(int i=0;i<4;i++)
		{
			if(r+dirx[i]>=1 && r+dirx[i]<=M && c+diry[i]>=1 && c+diry[i]<=N)
			{
				if(gr[r][c]>gr[r+dirx[i]][c+diry[i]])
				{
					valu = ceilf((gr[r][c]-gr[r+dirx[i]][c+diry[i]])*alpha1)+gema;
					tt = ceilf((gr[r][c]-gr[r+dirx[i]][c+diry[i]])*beta1)+delta;
				}
				else if(gr[r][c]<gr[r+dirx[i]][c+diry[i]])
				{
					valu = ceilf((gr[r+dirx[i]][c+diry[i]]-gr[r][c])*alpha2)+gema;
					tt = ceilf((gr[r+dirx[i]][c+diry[i]]-gr[r][c])*beta2)+delta;//gema
				}
				else if(gr[r][c]==gr[r+dirx[i]][c+diry[i]])
				{
					valu = gema;
					tt = delta;
				}

				if(en+valu>E)
					continue;
				if(visit[r+dirx[i]][c+diry[i]][en+valu])
					continue;
				visit[r+dirx[i]][c+diry[i]][en+valu] = 1;
				Time[r+dirx[i]][c+diry[i]][en+valu] = tm+tt;//Time[r][c][en]+tt;

				tstat.x = r+dirx[i];
				tstat.y = c+diry[i];
				tstat._energy = en+valu;
				tstat._time = tm+tt;//Time[r+dirx[i]][c+diry[i]][en+valu];
				q.push(tstat);
			}

		}
	}

	return Found;
}

int main()
{
	while(cin>>M)
	{
		cin>>N;

		if(M+N==0)
		break;
		cin>>alpha1>>alpha2>>gema;
		cin>>beta1>>beta2>>delta;

		for(int i=1;i<=M;i++)
		{
			for(int j=1;j<=N;j++)
				cin>>gr[i][j];
		}
		cin>>Rs>>Cs>>Rt>>Ct>>E;
		if(!bfs())
		cout<<"failed\n";//failed
		else
		cout<<MX<<"\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

#include <iostream>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cmath>

#define INF 100000000

using namespace std;

int M,N;

int gr[20][20];

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

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

float alpha1,alpha2;

int gema;

float beta1,beta2;

int delta;

int Rs,Cs,Rt,Ct;

int E;

int Time[20][20][205];

bool visit[20][20][205];

int MX;

struct State{

int x,y,_energy,_time;

};

struct cmp{

bool operator()(State one,State two)

{

return one._time<two._time;

}

};

bool bfs()

{

priority_queue<State,vector<State>,cmp> q;

MX = INF;

int valu,tt;

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

{

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

{

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

{

Time[i][j][k]=0;

visit[i][j][k]=false;

}

visit[Rs][Cs][0]=1;

State stat;

stat.x = Rs;stat.y = Cs,stat._energy = 0; stat._time = 0;

q.push(stat);

int r,c,en,tm;

Time[Rs][Cs][0]=0;

bool Found=0;

while(!q.empty())

{

State tstat = q.top();

q.pop();

r = tstat.x;//q.front();q.pop();

c = tstat.y;//q.front();q.pop();

en = tstat._energy;//q.front();q.pop();

tm = tstat._time;

if(r==Rt && c==Ct)

{

if(tm<MX)

{

MX = tm;//Time[r][c][en];

Found = 1;

}

continue;

}

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

{

if(r+dirx[i]>=1 && r+dirx[i]<=M && c+diry[i]>=1 && c+diry[i]<=N)

{

if(gr[r][c]>gr[r+dirx[i]][c+diry[i]])

{

valu = ceilf((gr[r][c]-gr[r+dirx[i]][c+diry[i]])*alpha1)+gema;

tt = ceilf((gr[r][c]-gr[r+dirx[i]][c+diry[i]])*beta1)+delta;

}

else if(gr[r][c]<gr[r+dirx[i]][c+diry[i]])

{

valu = ceilf((gr[r+dirx[i]][c+diry[i]]-gr[r][c])*alpha2)+gema;

tt = ceilf((gr[r+dirx[i]][c+diry[i]]-gr[r][c])*beta2)+delta;//gema

}

else if(gr[r][c]==gr[r+dirx[i]][c+diry[i]])

{

valu = gema;

tt = delta;

}

if(en+valu>E)

continue;

if(visit[r+dirx[i]][c+diry[i]][en+valu])

continue;

visit[r+dirx[i]][c+diry[i]][en+valu] = 1;

Time[r+dirx[i]][c+diry[i]][en+valu] = tm+tt;//Time[r][c][en]+tt;

tstat.x = r+dirx[i];

tstat.y = c+diry[i];

tstat._energy = en+valu;

tstat._time = tm+tt;//Time[r+dirx[i]][c+diry[i]][en+valu];

q.push(tstat);

}

return Found;

}

int main()

{

while(cin>>M)

{

cin>>N;

if(M+N==0)

break;

cin>>alpha1>>alpha2>>gema;

cin>>beta1>>beta2>>delta;

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

{

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

cin>>gr[i][j];

}

cin>>Rs>>Cs>>Rt>>Ct>>E;

if(!bfs())

cout<<"failed\n";//failed

else

cout<<MX<<"\n";

}

return 0;

}

589

Asif NaeemMarch 3, 2015

#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>

#define ll long long
#define INF 100000000

using namespace std;


struct INFO{
	string str;
	int CNT;
	int BX;
	int BY;
	int SX;
	int SY;
};

int MX;
string input[25];
int tx,ty;
int r,c;
string path="";
const int dirx[4]={-1,0,0,1};
const int diry[4]={0,1,-1,0};
const char Dir[6] = {'N','E','W','S'};
const  char dir[6] = {'n','e','w','s'};
map<int,bool> vis[25][25][25][25];


struct cmp {
    bool operator() (INFO a, INFO b) {
		if(a.CNT!=b.CNT)
        return a.CNT > b.CNT;

        return a.str.size()>b.str.size();
    }
};

bool check(int x,int y)
{
	if(x < 0 || x >= r || y < 0 || y >= c || input[x][y]!='.')
		return 0;
	return 1;
}
void BFS(int cnt,int bx,int by,int sx,int sy)
{
	vis[sx][sy][bx][by][0]=1;
	priority_queue<INFO,vector<INFO>,cmp> q;

	INFO info;

	info.str = "";
	info.CNT = cnt;
	info.BX = bx;
	info.BY = by;
	info.SX = sx;
	info.SY = sy;

	int x ,y;
	int distance;
	int srcx,srcy;

	q.push(info);
	while(!q.empty())
	{
		info = q.top();
		q.pop();

		x = info.BX;
		y = info.BY;
		distance=info.CNT;
		srcx = info.SX;
		srcy = info.SY;

		if(x==tx && y==ty)
		{
			if(distance<MX)
			{
				MX = distance;
				path = info.str;
			}
			else if(distance==MX)
			{
				if(info.str.size()<path.size())
					path = info.str;
			}
			else
			break;
			continue;
		}

		for(int i=0;i<4;i++)
		{
			INFO pINFO = info;



			pINFO.SX += dirx[i];
			pINFO.SY += diry[i];

			if(check(pINFO.SX,pINFO.SY)==0)
			continue;
			pINFO.str.append(1u,dir[i]);//char(Dir[i]+32);
			if(pINFO.SX == pINFO.BX && pINFO.SY==pINFO.BY)
			{
				pINFO.BX +=dirx[i];
				pINFO.BY +=diry[i];
				if(check(pINFO.BX,pINFO.BY)==0)
				continue;
				pINFO.CNT +=1;
				if(pINFO.CNT>MX)
				continue;
				//pINFO.str.erase(pINFO.str.begin()+(pINFO.str.size()-2));
				//pINFO.str.append(1u,Dir[i]);
				pINFO.str[pINFO.str.size()-1] = Dir[i];
			}

			if(vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()])
			continue;
			else
			{
				vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()] = 1;
				q.push(pINFO);
			}
		}

	}

}


int main()
{
	int tt=1;
	int bx,by,sx,sy;

	while(cin>>r)
	{
		cin>>c;

		if(r+c==0)
		break;

		for(int i=0;i<r;i++)
		{
			cin>>input[i];
			for(int j=0;j<c;j++)
			{
				if(input[i][j]=='S')
				{
					sx = i;
					sy = j;
				}
				else if(input[i][j]=='T')
				{
					tx = i;
					ty = j;
				}
				else if(input[i][j]=='B')
				{
					bx = i;
					by = j;
				}
				if(input[i][j]!='#')
					input[i][j]='.';
				for(int m=0;m<r;m++)
					for(int n=0;n<c;n++)
						vis[i][j][m][n].clear();
			}
		}
		path = "";
		MX = INF;
		BFS(0,bx,by,sx,sy);
		if(path.size()==0)
		{
			cout<<"Maze #"<<tt++<<"\n";
			cout<<"Impossible.\n\n";
		}
		else
		{
			cout<<"Maze #"<<tt++<<"\n";
			cout<<path<<"\n\n";
		}
	}//while loop

	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

#include <iostream>

#include <string.h>

#include <string>

#include <vector>

#include <map>

#include <queue>

#include <cstdio>

#include <cstdlib>

#define ll long long

#define INF 100000000

using namespace std;

struct INFO{

string str;

int CNT;

int BX;

int BY;

int SX;

int SY;

};

int MX;

string input[25];

int tx,ty;

int r,c;

string path="";

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

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

const char Dir[6] = {'N','E','W','S'};

const char dir[6] = {'n','e','w','s'};

map<int,bool> vis[25][25][25][25];

struct cmp {

bool operator() (INFO a, INFO b) {

if(a.CNT!=b.CNT)

return a.CNT > b.CNT;

return a.str.size()>b.str.size();

}

};

bool check(int x,int y)

{

if(x < 0 || x >= r || y < 0 || y >= c || input[x][y]!='.')

return 0;

return 1;

}

void BFS(int cnt,int bx,int by,int sx,int sy)

{

vis[sx][sy][bx][by][0]=1;

priority_queue<INFO,vector<INFO>,cmp> q;

INFO info;

info.str = "";

info.CNT = cnt;

info.BX = bx;

info.BY = by;

info.SX = sx;

info.SY = sy;

int x ,y;

int distance;

int srcx,srcy;

q.push(info);

while(!q.empty())

{

info = q.top();

q.pop();

x = info.BX;

y = info.BY;

distance=info.CNT;

srcx = info.SX;

srcy = info.SY;

if(x==tx && y==ty)

{

if(distance<MX)

{

MX = distance;

path = info.str;

}

else if(distance==MX)

{

if(info.str.size()<path.size())

path = info.str;

}

else

break;

continue;

}

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

{

INFO pINFO = info;

pINFO.SX += dirx[i];

pINFO.SY += diry[i];

if(check(pINFO.SX,pINFO.SY)==0)

continue;

pINFO.str.append(1u,dir[i]);//char(Dir[i]+32);

if(pINFO.SX == pINFO.BX && pINFO.SY==pINFO.BY)

{

pINFO.BX +=dirx[i];

pINFO.BY +=diry[i];

if(check(pINFO.BX,pINFO.BY)==0)

continue;

pINFO.CNT +=1;

if(pINFO.CNT>MX)

continue;

//pINFO.str.erase(pINFO.str.begin()+(pINFO.str.size()-2));

//pINFO.str.append(1u,Dir[i]);

pINFO.str[pINFO.str.size()-1] = Dir[i];

}

if(vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()])

continue;

else

{

vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()] = 1;

q.push(pINFO);

}

int main()

{

int tt=1;

int bx,by,sx,sy;

while(cin>>r)

{

cin>>c;

if(r+c==0)

break;

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

{

cin>>input[i];

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

{

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

{

sx = i;

sy = j;

}

else if(input[i][j]=='T')

{

tx = i;

ty = j;

}

else if(input[i][j]=='B')

{

bx = i;

by = j;

}

if(input[i][j]!='#')

input[i][j]='.';

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

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

vis[i][j][m][n].clear();

}

path = "";

MX = INF;

BFS(0,bx,by,sx,sy);

if(path.size()==0)

{

cout<<"Maze #"<<tt++<<"\n";

cout<<"Impossible.\n\n";

}

else

{

cout<<"Maze #"<<tt++<<"\n";

cout<<path<<"\n\n";

}

}//while loop

return 0;

}

Idea: Find the total number of matching and then check for every match(left,right) pair whether it is unique or not. To check this find total number of matching using the same algorithm just excluding a pair each time and compare the total number of founded match with the initial one. If it is not reduced

Continue Reading “663” →

1194

Asif NaeemMarch 3, 2015

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

using namespace std;

//int gr[105][105];
vector<int> gr[105];
int n,m,k;
int rside[105],lside[105];
bool visit[105];

bool dfs(int pos)
{
	for(int i=0;i<gr[pos].size();i++)
	{
		if(visit[gr[pos][i]])
		continue;

		visit[gr[pos][i]] = 1;

		if(lside[gr[pos][i]]==-1 || dfs(lside[gr[pos][i]]))
		{
			rside[pos] = gr[pos][i];
			lside[gr[pos][i]]= pos;
			return 1;
		}
	}
	return 0;
}

int main()
{
	int job,a,b;

	while(cin>>n)//row =machine A mode and colmn = machine B mode
	{
		if(n==0)
		break;
		cin>>m>>k;

		for(int i=0;i<105;i++)
		{
			gr[i].clear();
			rside[i]=-1;
			lside[i]=-1;
		}

		for(int i=0;i<k;i++)
		{
			cin>>job>>a>>b;
			if(!a || !b)
				continue;
			gr[a].push_back(b);
		}

		int res = 0;
		for(int i=0;i<n;i++)
		{
			memset(visit,0,sizeof(visit));
			if(dfs(i))
			res+=1;
		}
		cout<<res<<"\n";
	}

	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

#include <vector>

using namespace std;

//int gr[105][105];

vector<int> gr[105];

int n,m,k;

int rside[105],lside[105];

bool visit[105];

bool dfs(int pos)

{

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

{

if(visit[gr[pos][i]])

continue;

visit[gr[pos][i]] = 1;

if(lside[gr[pos][i]]==-1 || dfs(lside[gr[pos][i]]))

{

rside[pos] = gr[pos][i];

lside[gr[pos][i]]= pos;

return 1;

}

return 0;

}

int main()

{

int job,a,b;

while(cin>>n)//row =machine A mode and colmn = machine B mode

{

if(n==0)

break;

cin>>m>>k;

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

{

gr[i].clear();

rside[i]=-1;

lside[i]=-1;

}

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

{

cin>>job>>a>>b;

if(!a || !b)

continue;

gr[a].push_back(b);

}

int res = 0;

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

{

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

if(dfs(i))

res+=1;

}

cout<<res<<"\n";

}

return 0;

}

10080

Asif NaeemMarch 3, 2015

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

using namespace std;

int gr[105][105];
int N,M;
double S,V;

struct point{
	double x;
	double y;
};
point goph[105],hole[105];

// A DFS based recursive function that returns true if a
// matching for vertex u is possible
bool bpm(int u, bool seen[], int matchR[])
{
    // Try every hole one by one
    for (int v = 0; v < M; v++)
    {
        // If gopher u can reach in hole v and v is
        // not occupied
        if (gr[u][v] && !seen[v])
        {
            seen[v] = true; // Mark v as visited

            // If job 'v' is not assigned to a gopher OR
            // previously assigned gopher for hole v (which is matchR[v])
            // has an alternate hole available.
            // Since v is marked as visited in the above line, matchR[v]
            // in the following recursive call will not get hole 'v' again
            if (matchR[v] < 0 || bpm(matchR[v], seen, matchR))
            {
                matchR[v] = u;
                return true;
            }
        }
    }
    return false;
}

// Returns maximum number of matching from M to N
int maxBPM()
{
    // An array to keep track of the gophers assigned to
    // holes. The value of matchR[i] is the gopher number
    // assigned to hole i, the value -1 indicates nobody is
    // assigned.
    int matchR[M];

    // Initially all holes are available
    memset(matchR, -1, sizeof(matchR));

    int result = 0; // Count of holes assigned to gophers
    for (int u = 0; u < N; u++)
    {
        // Mark all holes as not seen for next gopher.
        bool seen[M];
        memset(seen, 0, sizeof(seen));

        // Find if the gopher 'u' can get a hole
        if (bpm(u, seen, matchR))
            result++;
    }
    return result;
}
int main()
{
	double a,b;
	double d,dist;
	while(scanf("%d%d%lf%lf",&N,&M,&S,&V)!=EOF)//n = gophr,m = hole
	{
		memset(gr,0,sizeof(gr));
		dist = S*V;
		for(int i=0;i<N;i++)
		{
			cin>>a>>b;
			goph[i].x = a;
			goph[i].y = b;
		}
		for(int i=0;i<M;i++)
		{
			cin>>a>>b;
			hole[i].x = a;
			hole[i].y = b;
		}

		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				d = sqrt((goph[i].x-hole[j].x)*(goph[i].x-hole[j].x)+(goph[i].y-hole[j].y)*(goph[i].y-hole[j].y));
				if(d<dist || (d-dist)<1e-7)//d<=dist
				gr[i][j] = 1;
			}
		}

		int mx = maxBPM();
		cout<<N-mx<<"\n";
	}
}

100

101

102

103

104

105

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

int gr[105][105];

int N,M;

double S,V;

struct point{

double x;

double y;

};

point goph[105],hole[105];

// A DFS based recursive function that returns true if a

// matching for vertex u is possible

bool bpm(int u, bool seen[], int matchR[])

{

// Try every hole one by one

for (int v = 0; v < M; v++)

{

// If gopher u can reach in hole v and v is

// not occupied

if (gr[u][v] && !seen[v])

{

seen[v] = true; // Mark v as visited

// If job 'v' is not assigned to a gopher OR

// previously assigned gopher for hole v (which is matchR[v])

// has an alternate hole available.

// Since v is marked as visited in the above line, matchR[v]

// in the following recursive call will not get hole 'v' again

if (matchR[v] < 0 || bpm(matchR[v], seen, matchR))

{

matchR[v] = u;

return true;

}

return false;

}

// Returns maximum number of matching from M to N

int maxBPM()

{

// An array to keep track of the gophers assigned to

// holes. The value of matchR[i] is the gopher number

// assigned to hole i, the value -1 indicates nobody is

// assigned.

int matchR[M];

// Initially all holes are available

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

int result = 0; // Count of holes assigned to gophers

for (int u = 0; u < N; u++)

{

// Mark all holes as not seen for next gopher.

bool seen[M];

memset(seen, 0, sizeof(seen));

// Find if the gopher 'u' can get a hole

if (bpm(u, seen, matchR))

result++;

}

return result;

}

int main()

{

double a,b;

double d,dist;

while(scanf("%d%d%lf%lf",&N,&M,&S,&V)!=EOF)//n = gophr,m = hole

{

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

dist = S*V;

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

{

cin>>a>>b;

goph[i].x = a;

goph[i].y = b;

}

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

{

cin>>a>>b;

hole[i].x = a;

hole[i].y = b;

}

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

{

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

{

d = sqrt((goph[i].x-hole[j].x)*(goph[i].x-hole[j].x)+(goph[i].y-hole[j].y)*(goph[i].y-hole[j].y));

if(d<dist || (d-dist)<1e-7)//d<=dist

gr[i][j] = 1;

}

int mx = maxBPM();

cout<<N-mx<<"\n";

}

532

Asif NaeemFebruary 15, 2015

#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue>

#define ll long long
#define INF 100000000
using namespace std;


int gr[32][32][32];
bool visit[32][32][32];
int dist[32][32][32];
int x,y,z;
int ex,ey,ez;
int L,R,C;



void bfs()
{
	int tmp_x,tmp_y,tmp_z;
	queue<int> q;
	q.push(x);
	q.push(y);
	q.push(z);

	visit[x][y][z]=1;
	dist[x][y][z] = 0;
	while(!q.empty())
	{
		tmp_x = q.front();
		q.pop();
		tmp_y = q.front();
		q.pop();
		tmp_z = q.front();
		q.pop();

		if(tmp_z+1<L && !visit[tmp_x][tmp_y][tmp_z+1] && gr[tmp_x][tmp_y][tmp_z+1]!=4)
		{
			visit[tmp_x][tmp_y][tmp_z+1]=1;
			dist[tmp_x][tmp_y][tmp_z+1] = min(dist[tmp_x][tmp_y][tmp_z+1],dist[tmp_x][tmp_y][tmp_z]+1);
			q.push(tmp_x);
			q.push(tmp_y);
			q.push(tmp_z+1);
		}
		if(tmp_z-1>=0 && !visit[tmp_x][tmp_y][tmp_z-1] && gr[tmp_x][tmp_y][tmp_z-1]!=4)
		{
			visit[tmp_x][tmp_y][tmp_z-1]=1;
			dist[tmp_x][tmp_y][tmp_z-1] = min(dist[tmp_x][tmp_y][tmp_z-1],dist[tmp_x][tmp_y][tmp_z]+1);
			q.push(tmp_x);
			q.push(tmp_y);
			q.push(tmp_z-1);
		}
		if(tmp_x+1<R && !visit[tmp_x+1][tmp_y][tmp_z] && gr[tmp_x+1][tmp_y][tmp_z]!=4)
		{
			visit[tmp_x+1][tmp_y][tmp_z]=1;
			dist[tmp_x+1][tmp_y][tmp_z] = min(dist[tmp_x+1][tmp_y][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);
			q.push(tmp_x+1);
			q.push(tmp_y);
			q.push(tmp_z);
		}
		if(tmp_x-1>=0 && !visit[tmp_x-1][tmp_y][tmp_z] && gr[tmp_x-1][tmp_y][tmp_z]!=4)
		{
			visit[tmp_x-1][tmp_y][tmp_z]=1;
			dist[tmp_x-1][tmp_y][tmp_z] = min(dist[tmp_x-1][tmp_y][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);
			q.push(tmp_x-1);
			q.push(tmp_y);
			q.push(tmp_z);
		}
		if(tmp_y-1>=0 && !visit[tmp_x][tmp_y-1][tmp_z] && gr[tmp_x][tmp_y-1][tmp_z]!=4)
		{
			visit[tmp_x][tmp_y-1][tmp_z]=1;
			dist[tmp_x][tmp_y-1][tmp_z] = min(dist[tmp_x][tmp_y-1][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);
			q.push(tmp_x);
			q.push(tmp_y-1);
			q.push(tmp_z);
		}
		if(tmp_y+1<C && !visit[tmp_x][tmp_y+1][tmp_z] && gr[tmp_x][tmp_y+1][tmp_z]!=4)
		{
			q.push(tmp_x);
			q.push(tmp_y+1);
			q.push(tmp_z);
			visit[tmp_x][tmp_y+1][tmp_z]=1;
			dist[tmp_x][tmp_y+1][tmp_z]=min(dist[tmp_x][tmp_y+1][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);
		}
	}
}


int main()
{
	char c;
	while(cin>>L)
	{
		cin>>R>>C;
		if(L+R+C==0)
		break;

		for(int i=0;i<L;i++)
		{
			for(int j=0;j<R;j++)
			{
				for(int k=0;k<C;k++)
				{
					dist[j][k][i]=INF;
					visit[j][k][i]=0;
					cin>>c;
					if(c=='S')
					{
						gr[j][k][i]=0;//src = 0
						x=j;y=k;z=i;//R,C,L
					}
					if(c=='E')
					{
						gr[j][k][i]=2;//exit = 2;
						ex=j;ey=k;ez=i;
					}
					if(c=='.')
					{
						gr[j][k][i]=1;//can move =1
					}
					if(c=='#')
					{
						gr[j][k][i]=4;//cant move = 4
					}
				}//1st for loop
			}//2nd for loop
			getchar();
		}//3rd for loop
		bfs();
		if(dist[ex][ey][ez]==INF)
		{
			cout<<"Trapped!\n";
		}
		else
		{
			cout<<"Escaped in ";
			cout<<dist[ex][ey][ez]<<" minute(s).\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

#include <iostream>

#include <string.h>

#include <vector>

#include <cstdio>

#include <queue>

#define ll long long

#define INF 100000000

using namespace std;

int gr[32][32][32];

bool visit[32][32][32];

int dist[32][32][32];

int x,y,z;

int ex,ey,ez;

int L,R,C;

void bfs()

{

int tmp_x,tmp_y,tmp_z;

queue<int> q;

q.push(x);

q.push(y);

q.push(z);

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

dist[x][y][z] = 0;

while(!q.empty())

{

tmp_x = q.front();

q.pop();

tmp_y = q.front();

q.pop();

tmp_z = q.front();

q.pop();

if(tmp_z+1<L && !visit[tmp_x][tmp_y][tmp_z+1] && gr[tmp_x][tmp_y][tmp_z+1]!=4)

{

visit[tmp_x][tmp_y][tmp_z+1]=1;

dist[tmp_x][tmp_y][tmp_z+1] = min(dist[tmp_x][tmp_y][tmp_z+1],dist[tmp_x][tmp_y][tmp_z]+1);

q.push(tmp_x);

q.push(tmp_y);

q.push(tmp_z+1);

}

if(tmp_z-1>=0 && !visit[tmp_x][tmp_y][tmp_z-1] && gr[tmp_x][tmp_y][tmp_z-1]!=4)

{

visit[tmp_x][tmp_y][tmp_z-1]=1;

dist[tmp_x][tmp_y][tmp_z-1] = min(dist[tmp_x][tmp_y][tmp_z-1],dist[tmp_x][tmp_y][tmp_z]+1);

q.push(tmp_x);

q.push(tmp_y);

q.push(tmp_z-1);

}

if(tmp_x+1<R && !visit[tmp_x+1][tmp_y][tmp_z] && gr[tmp_x+1][tmp_y][tmp_z]!=4)

{

visit[tmp_x+1][tmp_y][tmp_z]=1;

dist[tmp_x+1][tmp_y][tmp_z] = min(dist[tmp_x+1][tmp_y][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);

q.push(tmp_x+1);

q.push(tmp_y);

q.push(tmp_z);

}

if(tmp_x-1>=0 && !visit[tmp_x-1][tmp_y][tmp_z] && gr[tmp_x-1][tmp_y][tmp_z]!=4)

{

visit[tmp_x-1][tmp_y][tmp_z]=1;

dist[tmp_x-1][tmp_y][tmp_z] = min(dist[tmp_x-1][tmp_y][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);

q.push(tmp_x-1);

q.push(tmp_y);

q.push(tmp_z);

}

if(tmp_y-1>=0 && !visit[tmp_x][tmp_y-1][tmp_z] && gr[tmp_x][tmp_y-1][tmp_z]!=4)

{

visit[tmp_x][tmp_y-1][tmp_z]=1;

dist[tmp_x][tmp_y-1][tmp_z] = min(dist[tmp_x][tmp_y-1][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);

q.push(tmp_x);

q.push(tmp_y-1);

q.push(tmp_z);

}

if(tmp_y+1<C && !visit[tmp_x][tmp_y+1][tmp_z] && gr[tmp_x][tmp_y+1][tmp_z]!=4)

{

q.push(tmp_x);

q.push(tmp_y+1);

q.push(tmp_z);

visit[tmp_x][tmp_y+1][tmp_z]=1;

dist[tmp_x][tmp_y+1][tmp_z]=min(dist[tmp_x][tmp_y+1][tmp_z],dist[tmp_x][tmp_y][tmp_z]+1);

}

int main()

{

char c;

while(cin>>L)

{

cin>>R>>C;

if(L+R+C==0)

break;

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

{

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

{

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

{

dist[j][k][i]=INF;

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

cin>>c;

if(c=='S')

{

gr[j][k][i]=0;//src = 0

x=j;y=k;z=i;//R,C,L

}

if(c=='E')

{

gr[j][k][i]=2;//exit = 2;

ex=j;ey=k;ez=i;

}

if(c=='.')

{

gr[j][k][i]=1;//can move =1

}

if(c=='#')

{

gr[j][k][i]=4;//cant move = 4

}

}//1st for loop

}//2nd for loop

getchar();

}//3rd for loop

bfs();

if(dist[ex][ey][ez]==INF)

{

cout<<"Trapped!\n";

}

else

{

cout<<"Escaped in ";

cout<<dist[ex][ey][ez]<<" minute(s).\n";

}

return 0;

}

Category: Graph Algorithm

124

452

10937

10349

10076

589

663

1194

10080

532

Archives

Categories