March 2015 – Live with passion

166

Asif NaeemMarch 31, 2015

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <fstream>

#define INF 10000000
using namespace std;

int availabe_coin[6];
int min_ways[1005];
int visit[6];
int coins[6]={5,10,20,50,100,200};
int cost;
int cmp;

void dp(int tcost,int index,int noOfsteps)
{
	int tmp,v;
	if(tcost>=cost)
	{
		int d = tcost-cost;
		if(d>1003)
		return;
		if(min_ways[d]!=INF)
		{
			tmp = noOfsteps+min_ways[tcost-cost];
			if(tmp<cmp)
			{
				cmp = tmp;
				return;
			}
		}
	}
	for(int i=index+1;i<6;i++)
	{
		if(availabe_coin[i]==0)
		continue;
		if(visit[i]==0)
		{
			visit[i]=1;
			v = availabe_coin[i];
			for(int j=1;j<=v;j++)
			{
				availabe_coin[i]-=j;
				dp(tcost+j*coins[i],i,noOfsteps+j);
				availabe_coin[i]+=j;
			}
			visit[i]=0;
		}
	}
}

int main()
{
	int total,v,p,q;
	for(int i=0;i<1005;i++)
		min_ways[i]=INF;

	min_ways[0]=0;

	for(int i=0;i<6;i++)
	{
		for(int j=coins[i];j<1005;j++)
		{
			min_ways[j]= min(min_ways[j],1+min_ways[j-coins[i]]);
		}
	}
	while(scanf("%d",&availabe_coin[0]))
	{
		visit[0]=0;
		total = availabe_coin[0];
		for(int i=1;i<=5;i++)
		{
			scanf("%d",&availabe_coin[i]);
			visit[i]=0;
			total += availabe_coin[i];
		}
		if(total==0)
		break;

		scanf("%d.%d",&p,&q);
		cost=q+p*100;
		cmp = INF;
		for(int i=0;i<6;i++)
		{
			if(availabe_coin[i]==0)
			continue;
			if(visit[i]==0)
			{
				visit[i]=1;
				v = availabe_coin[i];
				for(int j=1;j<=v;j++)
				{
					availabe_coin[i]-=j;
					dp(0+j*coins[i],i,0+j);
					availabe_coin[i]+=j;
				}
				visit[i]=0;
			}
		}
		cout<<setw(3)<<cmp<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <iomanip>

#include <fstream>

#define INF 10000000

using namespace std;

int availabe_coin[6];

int min_ways[1005];

int visit[6];

int coins[6]={5,10,20,50,100,200};

int cost;

int cmp;

void dp(int tcost,int index,int noOfsteps)

{

int tmp,v;

if(tcost>=cost)

{

int d = tcost-cost;

if(d>1003)

return;

if(min_ways[d]!=INF)

{

tmp = noOfsteps+min_ways[tcost-cost];

if(tmp<cmp)

{

cmp = tmp;

return;

}

for(int i=index+1;i<6;i++)

{

if(availabe_coin[i]==0)

continue;

if(visit[i]==0)

{

visit[i]=1;

v = availabe_coin[i];

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

{

availabe_coin[i]-=j;

dp(tcost+j*coins[i],i,noOfsteps+j);

availabe_coin[i]+=j;

}

visit[i]=0;

}

int main()

{

int total,v,p,q;

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

min_ways[i]=INF;

min_ways[0]=0;

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

{

for(int j=coins[i];j<1005;j++)

{

min_ways[j]= min(min_ways[j],1+min_ways[j-coins[i]]);

}

while(scanf("%d",&availabe_coin[0]))

{

visit[0]=0;

total = availabe_coin[0];

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

{

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

visit[i]=0;

total += availabe_coin[i];

}

if(total==0)

break;

scanf("%d.%d",&p,&q);

cost=q+p*100;

cmp = INF;

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

{

if(availabe_coin[i]==0)

continue;

if(visit[i]==0)

{

visit[i]=1;

v = availabe_coin[i];

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

{

availabe_coin[i]-=j;

dp(0+j*coins[i],i,0+j);

availabe_coin[i]+=j;

}

visit[i]=0;

}

cout<<setw(3)<<cmp<<"\n";

}

return 0;

}

10912

Asif NaeemMarch 29, 2015

#include <iostream>

using namespace std;

int L,S;
int dp[27][352][27];//[length][total][last element]
int res_dp[27][352];

int main()
{
	int kase=1;
	for(int i=1;i<27;i++)
	{
		dp[1][i][i]=1;
	}
	for(int i=2;i<=26;i++)//length of the string
		for(int j=1;j<=351;j++)//sum of all the value
			for(int k=1;k<=26;k++)//max last ending value
				for(int ll=1;ll<k;ll++)
				{
					dp[i][j][k]+=dp[i-1][j-k][ll];
				}

	for(int i=1;i<=26;i++)
		for(int j=1;j<=351;j++)
			for(int k=1;k<=26;k++)
				res_dp[i][j]+=dp[i][j][k];
	while(cin>>L)
	{
		cin>>S;
		if(L+S==0)
		break;

		cout<<"Case "<<kase++<<": ";
		if(L>0 && L<=26 && S>0 && S<=351)
			cout<<res_dp[L][S]<<"\n";
		else
			cout<<0<<"\n";
	}

	return 0;
}

#include <iostream>

using namespace std;

int L,S;

int dp[27][352][27];//[length][total][last element]

int res_dp[27][352];

int main()

{

int kase=1;

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

{

dp[1][i][i]=1;

}

for(int i=2;i<=26;i++)//length of the string

for(int j=1;j<=351;j++)//sum of all the value

for(int k=1;k<=26;k++)//max last ending value

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

{

dp[i][j][k]+=dp[i-1][j-k][ll];

}

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

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

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

res_dp[i][j]+=dp[i][j][k];

while(cin>>L)

{

cin>>S;

if(L+S==0)

break;

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

if(L>0 && L<=26 && S>0 && S<=351)

cout<<res_dp[L][S]<<"\n";

else

cout<<0<<"\n";

}

return 0;

}

116

Asif NaeemMarch 28, 2015

#include <iostream>
#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;
int input[11][101];
int dp[11][101];
int next_row[11][101];

int main()
{
	int tmp,temp_position,row;

	while(scanf("%d%d",&r,&c)==2)
	{
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				cin>>input[i][j];

		for(int i=0;i<r;i++)
			dp[i][c-1]=input[i][c-1];

		for(int i=c-2;i>=0;i--)
		{
			for(int j=0;j<r;j++)
			{
				tmp=MX;

				for(int k=-1;k<=1;k++)
				{
					temp_position = (j+k+r)%r;

					if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))
					{
						next_row[j][i]=temp_position;
						tmp = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}

#include <iostream>

#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;

int input[11][101];

int dp[11][101];

int next_row[11][101];

int main()

{

int tmp,temp_position,row;

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

{

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

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

cin>>input[i][j];

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

dp[i][c-1]=input[i][c-1];

for(int i=c-2;i>=0;i--)

{

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

{

tmp=MX;

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

{

temp_position = (j+k+r)%r;

if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))

{

next_row[j][i]=temp_position;

tmp = dp[temp_position][i+1];

}

dp[j][i]=input[j][i]+tmp;

}

tmp = MX;

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

{

if(tmp>dp[i][0])

{

tmp = dp[i][0];

row = i;

}

cout<<row+1;

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

{

row = next_row[row][i];

cout<<" "<<row+1;

}

cout<<"\n"<<tmp<<"\n";

}

return 0;

}

#include <iostream>
#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;
int input[11][101];
int dp[11][101];
int next_row[11][101];

int main()
{
	int tmp,temp_position,row;

	while(scanf("%d%d",&r,&c)==2)
	{
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				cin>>input[i][j];

		for(int i=0;i<r;i++)
			dp[i][c-1]=input[i][c-1];

		for(int i=c-2;i>=0;i--)
		{
			for(int j=0;j<r;j++)
			{
				tmp=MX;

				for(int k=-1;k<=1;k++)
				{
					temp_position = (j+k+r)%r;

					if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))
					{
						next_row[j][i]=temp_position;
						tmp = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}

#include <iostream>

#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;

int input[11][101];

int dp[11][101];

int next_row[11][101];

int main()

{

int tmp,temp_position,row;

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

{

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

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

cin>>input[i][j];

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

dp[i][c-1]=input[i][c-1];

for(int i=c-2;i>=0;i--)

{

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

{

tmp=MX;

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

{

temp_position = (j+k+r)%r;

if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))

{

next_row[j][i]=temp_position;

tmp = dp[temp_position][i+1];

}

dp[j][i]=input[j][i]+tmp;

}

tmp = MX;

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

{

if(tmp>dp[i][0])

{

tmp = dp[i][0];

row = i;

}

cout<<row+1;

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

{

row = next_row[row][i];

cout<<" "<<row+1;

}

cout<<"\n"<<tmp<<"\n";

}

return 0;

}

196

Asif NaeemMarch 26, 2015

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <string>
#include <cmath>
#include <sstream>

using namespace std;

string str[1000][18279];
int val[1000][18279];
bool isDone[1000][18279];
int C,R;

int solve(int a,int b)
{
	if(isDone[a][b])
	return val[a][b];
	string tmpstr;

	for(int i=0;i<str[a][b].size();i++)
	{
		if(str[a][b][i]=='=' || str[a][b][i]=='+')
		{
			str[a][b][i]=' ';
		}
	}
	stringstream ss;
	ss<<str[a][b];

	int sum = 0;
	tmpstr="";
	while(ss>>tmpstr)
	{
		int r = 0;
		int c = 0;
		for(int j=0;j<tmpstr.size();j++)
		{
			if(tmpstr[j]>='0' && tmpstr[j]<='9')
			{
				r=r*10+(tmpstr[j]-'0');
			}
			else
			{
				c = c*26+(tmpstr[j]-'A'+1);
			}
		}
		int tt = solve(r,c);
		sum+=tt;

	}
	isDone[a][b]=1;
	return (val[a][b]=sum);
}


int toint(string st)
{
	int sum = 0;
	for(int i=0;i<st.size();i++)
	{
		sum = sum*10+(st[i]-'0');
	}
	return sum;
}

int main()
{
	int t;
	cin>>t;

	while(t--)
	{
		cin>>C>>R;

		for(int i=1;i<=R;i++)
		{
			for(int j=1;j<=C;j++)
			{
				cin>>str[i][j];
				isDone[i][j]=0;
				if(str[i][j][0]>='0' && str[i][j][0]<='9')
				{
					val[i][j]=toint(str[i][j]);
					isDone[i][j]=1;
				}
			}
		}
		for(int i=1;i<=R;i++)
			for(int j=1;j<=C;j++)
				cout<<solve(i,j)<<(j==C?"\n":" ");
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <string>

#include <cmath>

#include <sstream>

using namespace std;

string str[1000][18279];

int val[1000][18279];

bool isDone[1000][18279];

int C,R;

int solve(int a,int b)

{

if(isDone[a][b])

return val[a][b];

string tmpstr;

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

{

if(str[a][b][i]=='=' || str[a][b][i]=='+')

{

str[a][b][i]=' ';

}

stringstream ss;

ss<<str[a][b];

int sum = 0;

tmpstr="";

while(ss>>tmpstr)

{

int r = 0;

int c = 0;

for(int j=0;j<tmpstr.size();j++)

{

if(tmpstr[j]>='0' && tmpstr[j]<='9')

{

r=r*10+(tmpstr[j]-'0');

}

else

{

c = c*26+(tmpstr[j]-'A'+1);

}

int tt = solve(r,c);

sum+=tt;

}

isDone[a][b]=1;

return (val[a][b]=sum);

}

int toint(string st)

{

int sum = 0;

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

{

sum = sum*10+(st[i]-'0');

}

return sum;

}

int main()

{

int t;

cin>>t;

while(t--)

{

cin>>C>>R;

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

{

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

{

cin>>str[i][j];

isDone[i][j]=0;

if(str[i][j][0]>='0' && str[i][j][0]<='9')

{

val[i][j]=toint(str[i][j]);

isDone[i][j]=1;

}

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

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

cout<<solve(i,j)<<(j==C?"\n":" ");

}

return 0;

}

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;

}

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;

}

Month: March 2015

166

10912

116

196

872

124

452

10937

10349

10076

Archives

Categories