| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
bfs第一次过#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
struct State{
int i, j;
vector<int> steps;
};
int vis[105][105];
int a, b, c;
void print(vector<int> t)
{
if(!t.empty())
{
cout << t.size() << endl;
for(int i = 0; i < t.size(); i++)
if(t[i] == 1)
cout << "FILL(1)\n";
else if(t[i] == 2)
cout << "DROP(1)\n";
else if(t[i] == 3)
cout << "POUR(1,2)\n";
else if(t[i] == 4)
cout << "FILL(2)\n";
else if(t[i] == 5)
cout << "DROP(2)\n";
else if(t[i] == 6)
cout << "POUR(2,1)\n";
else
continue;
}
else
cout << "impossible\n";
}
void bfs(State p)
{
queue<State> Q;
memset(vis, 0, sizeof(vis));
Q.push(p);
vis[p.i][p.j] = 1;
while(!Q.empty())
{
State tmp = Q.front();
Q.pop();
if(tmp.i == c || tmp.j == c)
{
print(tmp.steps);
return ;
}
State np = tmp;
np.i = a;
np.j = tmp.j;
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(1);
Q.push(np);
}
np = tmp;
np.i = 0;
np.j = tmp.j;
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(2);
Q.push(np);
}
np = tmp;
int cha = b - tmp.j;
if(np.i >= cha)
{
np.j = b;
np.i = tmp.i - cha;
}
else
{
np.j = tmp.j + tmp.i;
np.i = 0;
}
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(3);
Q.push(np);
}
np = tmp;
np.j = b;
np.i = tmp.i;
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(4);
Q.push(np);
}
np = tmp;
np.j = 0;
np.i = tmp.i;
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(5);
Q.push(np);
}
np = tmp;
cha = a - tmp.i;
if(np.j >= cha)
{
np.i = a;
np.j = tmp.j - cha;
}
else
{
np.i = tmp.j + tmp.i;
np.j = 0;
}
if(!vis[np.i][np.j])
{
vis[np.i][np.j] = 1;
np.steps.push_back(6);
Q.push(np);
}
}
cout << "impossible\n" << endl;
}
int main()
{
cin >> a >> b >> c;
vector<int> q;
bfs(State{0, 0, q});
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator