广搜超进阶
广搜超进阶
练习
P1432 倒水问题
思路
我的思路就是首先根据题目来讲这一道题，题目的要求就是b水壶的谁的水量刚刚好就是n。而这题目有几种操作。
1，就是将某个水桶倒满。
2，把某个水桶的水倒给另一个水桶.
3，将某个水桶的水倒掉。
根据这些操作就可以发现算起来就是6种操作那么我们就可以广搜去搜索6种操作而每搜一种就存下来最后逆推找出答案。
代码
#include<bits/stdc++.h>
using namespace std;
int x,y,n,k;
int d[1000005][5],b[1005][1005],m[1000005],a[100005],p1,p2,f,xx,yy;
void bfs(){
while(p1 <= p2 && f == 0){
for(int i = 1 ; i <= 6 ; i ++){
xx = d[p1][1];
yy = d[p1][2];
if(i == 1){
xx = x;
}
if(i == 2){
yy = y;
}
if(i == 3){
xx = 0;
}
if(i == 4){
yy = 0;
}
if(i == 5){
if(xx + yy>x){
yy = xx + yy - x;
xx = x;
}else{
xx = xx + yy;
yy = 0;
}
}
if(i == 6){
if(xx + yy > y){
xx = xx + yy - y;
yy = y;
}else{
yy = xx + yy;
xx = 0;
}
}
if(b[xx][yy] == 0){
p2 ++;
d[p2][3] = i;
d[p2][4] = p1;
d[p2][1] = xx;
d[p2][2] = yy;
b[xx][yy] ++;
m[p2] = m[p1] + 1;
if(d[p2][2] == n){
f ++;
break;
}
}
}
p1 ++;
}
}
int main(){
cin >> k;
for(int i = 1 ; i <= k ; i ++){
cin >> x >> y >> n;
memset(b,0,sizeof(b));
b[0][0] = 1;
p1 = 1;
p2 = 1;
f = 0;
bfs();
int p = p2,len = 0;
while(d[p][4] > 0){
len ++;
a[len] = d[p][3];
p = d[p][4];
}
cout << m[p2] << " ";
for(int j = len ; j >= 1 ; j --){
cout << a[j] << " ";
}
cout << endl;
}
return 0;
}P1032 [NOIP2002 提高组] 字串变换
思路
在讲正确思路之前我们先来了解一个函数——substr（）。这个函数的作用我们可以来做一个选择题。
A.获取字符串中的子串
B.分割字符串
C.获取字符最后一次出现的位置
D.替换字符串
答案已经十分明显了,那就是A。
那么我们的思路就已经十分明显了，就是一道普通的广搜加上上面那个函数的判断，毕竟是替换。
首先要注意的是这次广搜的标记是
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct pi{
string x;
int step;
};
string s,z,a[10005],b[10005];
ll cnt = 1;
map<string,bool>vis;
int bfs(){
if(s == z){
return 0;
}
queue<pi> q;
q.push({s,0});
vis[s] = 1;
while(!q.empty()){
pi u = q.front();
q.pop();
if(u.step == 10) continue;
for(int i = 1 ; i <= cnt ; i ++){
for(int j = 0 ; j < int(u.x.size()) - int(a[i].size()) + 1 ; j ++){
if(u.x.substr(j , a[i].size()) == a[i]){
string y = u.x.substr(0,j);
y += b[i];
y += u.x.substr(j + int(a[i].size()),int(u.x.size()) - j - int(a[i].size()));
if(y == z){
return u.step + 1;
}
q.push({y,u.step + 1});
vis[y] = 1;
}
}
}
}
return -1;
}
int main(){
cin >> s >> z;
z = ' ' + z;
s = ' ' + s;
while(cin >> a[cnt] >> b[cnt])cnt ++;
cnt --;
int k = bfs();
if(k == -1){
cout << "NO ANSWER!";
}else{
cout << k;
}
return 0;
}Lucky Numbers (easy)
思路
这题咱们可以先来看看范围，然后你就会发现想从
当然除非你只想要一点分，但是我们难道是只要那么点分的人吗嗯~我是。
那么我们就因该来观察~~。你看最小那个地方对吧，想要最小是加4还是加7呢？很显然想加4。
那么我们来看看加入一开始时4和7那么就先加4再加7就是44，47，74，77刚好时从小到大的。
那么事情就是分简单了，直接疯狂往后加4或7再判断是否大于要找的数输出即可。这道题是不要标记的你看这题每次只会往后加上数所以不可能与上一次一样的。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dx[] = {4 , 7},n;
bool check(int x)
{
int sum = 0,num = 0;
while(x > 0){
if(x % 10 == 4)sum ++;
else num ++;
x /= 10;
}
return sum == num;
}
int bfs(){
queue<int>q;
q.push(4);
q.push(7);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0 ; i < 2 ; i ++){
int xx = x * 10 + dx[i];
if(xx >= n && check(xx)){
return xx;
}
q.push(xx);
}
}
}
signed main(){
cin >> n;
cout << bfs();
return 0;
}
Required Length
思路
这题其实也就只有几个坑点，只要把这几个坑点解决了那么一切都解决了。
坑点1，0或者1不能进栈，你看0相乘之后就是0了所以不能进至于1都没改变也不能进。
坑点2，这一的标记你要是用bool 那么你将会带上痛苦面具，
坑点3，十分的明显的坑点，要开long long。
这题避开那几个坑点就十分好做了，我们用一个数存下u.x然后不断除，模找出每个数相乘再看看能不能进队列如果位数达到了就输出操作次数。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct pi{
int x,step;
};
bool check(int x){
int sum = 0;
while(x > 0){
sum ++;
x /= 10;
}
return sum == n;
}
map<long long ,int>mp;
int bfs(){
queue<pi>q;
q.push({m , 0});
if(check(m))return 0;
mp[m] = 1;
while(!q.empty()){
pi u = q.front();
q.pop();
int xx = u.x;
while(xx > 0){
if(xx % 10 <= 1){
xx /= 10;
continue;
}
if(mp[u.x * (xx % 10)]){
xx /= 10;
continue;
}
if(check(u.x * (xx % 10))){
return u.step + 1;
}
mp[u.x * (xx % 10)] ++;
q.push({u.x * (xx % 10) , u.step + 1});
xx /= 10;
}
}
return -1;
}
signed main(){
cin >> n >> m;
cout << bfs();
return 0;
}
课后作业
P1135 奇怪的电梯
P1033 [NOIP2002 提高组] 自由落体
P1141 01迷宫
P2730 [USACO3.2] 魔板 Magic Squares