[kuangbin带你飞]专题一 简单搜索

[kuangbin带你飞]专题一 简单搜索

算法：sf / /  错误点：w  // 注意细节：xj

第一题 POJ 1321

sf：dfs  xj：在于状态函数的标记和取消

　　这里输入使用了  ch = getchar() 抓取字符。

　　因为要找出所有方法数，所以暴力dfs就可以了。

#include 
#include 
#include 

using namespace std;

int n,k,ck;
char ch;
bool h[10],l[10],fk[10][10];
long long ans;

void init(){
    memset(h,false,sizeof h);
    memset(l,false,sizeof l);
    memset(fk,false,sizeof fk);
    ans=0;ck=0;
    for(int i=0;i)
        for(int j=0;j){
            ch=getchar();
            if(ch=='\n') ch=getchar();
            if(ch=='#') fk[i][j]=true,ck++;
        }
}

void dfs(int a,int b,int c){
    if(c==k) ans++;
    else{
        for(int i=a+1;i){
            if(h[i]) continue;
            for(int j=0;j){
                if(l[j]) continue;
                if(fk[i][j]){
                    h[i]=true;l[j]=true;
                    dfs(i,j,c+1);
                    h[i]=false;l[j]=false;
                }
            }
        }
    }
}

int main()
{
    while(cin>>n>>k){
        if(n==-1&&k==-1) break;
        init();
        for(int i=0;i=k;i++)
            for(int j=0;j=k;j++)
                if(fk[i][j]){
                    h[i]=true;l[j]=true;
                    dfs(i,j,1);
                    h[i]=false;l[j]=false;
                    ck--;
                }
        cout<endl;
    }

    return 0;
}

第二题POJ - 2251 

sf：bfs xj：在于三维的迷宫 用三维状态函数

#include 
#include 
#include 
#include 

using namespace std;

int l,r,c;
char ch;
bool fk[31][31][31];
bool cp;

struct node{
    int z,x,y;
    int cc;
};

node k,j;
queue q;

void init(){
    cp=false;
    memset(fk,false,sizeof fk);
    for(int z=1;z<=l;z++)
        for(int x=1;x<=r;x++)
            for(int y=1;y<=c;y++){
                ch=getchar();
                while(ch=='\n') ch=getchar();
                if(ch=='S') k.cc=0,k.x=x,k.y=y,k.z=z;
                if(ch=='E') j.x=x,j.y=y,j.z=z;
                if(ch=='E'||ch=='.') fk[z][x][y]=true;
            }
}

bool check(int z,int x,int y){
    if(z<1||z>l) return false;
    if(x<1||x>r) return false;
    if(y<1||y>c) return false;
    if(fk[z][x][y]) return true;
    return false;
}

int main()
{
    while(cin>>l>>r>>c){
        if(l==0&&r==0&&c==0) break;
        init();
        q.push(k);
        while(!q.empty()){
            node n = q.front();q.pop();
            if(n.x==j.x&&n.z==j.z&&n.y==j.y) {cout<<"Escaped in "<" minute(s)."<true;break;}
            if(check(n.z-1,n.x,n.y)) {node m = n;m.z--;m.cc++;q.push(m);fk[n.z-1][n.x][n.y]=false;}
            if(check(n.z+1,n.x,n.y)) {node m = n;m.z++;m.cc++;q.push(m);fk[n.z+1][n.x][n.y]=false;}
            if(check(n.z,n.x-1,n.y)) {node m = n;m.x--;m.cc++;q.push(m);fk[n.z][n.x-1][n.y]=false;}
            if(check(n.z,n.x+1,n.y)) {node m = n;m.x++;m.cc++;q.push(m);fk[n.z][n.x+1][n.y]=false;}
            if(check(n.z,n.x,n.y-1)) {node m = n;m.y--;m.cc++;q.push(m);fk[n.z][n.x][n.y-1]=false;}
            if(check(n.z,n.x,n.y+1)) {node m = n;m.y++;m.cc++;q.push(m);fk[n.z][n.x][n.y+1]=false;}
        }
        while(!q.empty()) q.pop();
        if(!cp) cout<<"Trapped!"<<endl;
    }
    return 0;
}

POJ - 3278 

sf：bfs 难点：在于判断  当超过目标不需要 +1

#include 
#include 
#include 
#include 

using namespace std;

const int M = 1e5;
int n,k;
int cp[M+5];
queue<int> q;

int main()
{
    memset(cp,-1,sizeof cp);
    cin>>n>>k;
    cp[n]=0;
    q.push(n);
    while(!q.empty()){
        int m=q.front();q.pop();
        if(m==k) break;
        if(m*2<=M&&cp[m*2]<0) {q.push(m*2);cp[m*2]=cp[m]+1;}
        if(m+1<=k&&cp[m+1]<0) {q.push(m+1);cp[m+1]=cp[m]+1;}
        if(m>=1&&cp[m-1]<0) {q.push(m-1);cp[m-1]=cp[m]+1;}
    }
    cout << cp[k] << endl;
    return 0;
}

POJ - 3279 

sf：暴力枚举第一行的情况（用2进制） 然后每下一行的操作取决于上一行是否存在1

#include 
#include 
#include 

using namespace std;

#define inf 1e9

long long cnt,tt;
int n,m;
char ch;
int ans[20][20],akb[20][20];
bool fk[20][20],jk[20][20];

void init(){
    cnt=inf;
    memset(jk,false,sizeof jk);
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++){
        ch=getchar();
        while(ch=='\n'||ch==' ') ch=getchar();
        if(ch=='1') jk[i][j]=true;
    }
}

void check(int i,int j){
    if(fk[i][j]) fk[i][j]=false;
    else fk[i][j]=true;
    if(fk[i+1][j]) fk[i+1][j]=false;
    else fk[i+1][j]=true;
    if(fk[i+1][j+1]) fk[i+1][j+1]=false;
    else fk[i+1][j+1]=true;
    if(fk[i+1][j-1]) fk[i+1][j-1]=false;
    else fk[i+1][j-1]=true;
    if(fk[i+2][j]) fk[i+2][j]=false;
    else fk[i+2][j]=true;
}

void check2(int i,int j){
    if(fk[i][j]) fk[i][j]=false;
    else fk[i][j]=true;
    if(fk[i][j+1]) fk[i][j+1]=false;
    else fk[i][j+1]=true;
    if(fk[i][j-1]) fk[i][j-1]=false;
    else fk[i][j-1]=true;
    if(fk[i+1][j]) fk[i+1][j]=false;
    else fk[i+1][j]=true;
}

bool go(){
    for(int i=1;i)
        for(int j=1;j<=n;j++)
            if(fk[i][j]){
                check(i,j);
                tt++;if(tt>=cnt) return false;
                ans[i+1][j]++;
            }
    for(int j=1;j<=n;j++) if(fk[m][j]) return false;
    return true;
}

void solve(int x){
    tt=0;memset(ans,0,sizeof ans);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            fk[i][j]=jk[i][j];
    for(int i=0;iif((1<1,i+1);ans[1][i+1]++;tt++;if(tt>=cnt) return ;}
    if(go()){
        cnt=tt;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++) akb[i][j]=ans[i][j];
    }
}

int main()
{
    cin>>m>>n;
    init();
    for(int i=0;i<(1<) solve(i);
    if(cnt==inf) cout<<"IMPOSSIBLE"<<endl;
    else {
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++)
                cout<' ';
            cout<<endl;
        }
    }
    return 0;
}

POJ - 1426 

sf：bfs  余数*10+0/1  或者 直接dfs

#include 
#include 
#include 
#include <string>
#include 

using namespace std;

int n;
bool fk[201];

struct node{
    int a;
    string str;
};
node k;

int main()
{
    while(cin>>n&&n!=0){
        memset(fk,false,sizeof fk);
        k.a = 1%n;k.str = "1";fk[k.a] = true;
        queue q;q.push(k);
        while(!q.empty()){
            node p = q.front();q.pop();
            int a = p.a;string str = p.str;
            if(a==0) {cout<break;}
            else{
                node m;
                m.a = a*10%n, m.str = str + "0";
                if(!fk[m.a]) q.push(m),fk[m.a] = true;
                m.a = (a*10+1)%n, m.str = str + "1";
                if(!fk[m.a]) q.push(m),fk[m.a] = true;
            }
        }
    }
    return 0;
}
#include 
#include 

using namespace std;

int n,flag;

void dfs(unsigned long long a,int step){
    if(flag||step==50) return ;
    if(a%n==0) {flag = 1;printf("%I64u\n",a);return ;}
    else{
        dfs(a*10,step+1);
        dfs(a*10+1,step+1);
    }
}

int main()
{
    while(~scanf("%d",&n)&&n){
        flag = 0;
        dfs(1,0);
    }
    return 0;
}

POJ - 3126 

sf：求质数 + bfs  

#include 
#include 
#include 

using namespace std;

int n,m;
int y[5];
int ans[10000];
queue<int> q;

bool check(int x){
    for(int i=2;i*i<=x;i++) if(x%i==0) return false;
    return true;
}

void go(int x){
    for(int i=1;i<=4;i++){
        y[i]=x%10;
        x/=10;
    }
}

void dfs(){
    memset(ans,-1,sizeof ans);
    q.push(n);ans[n]=0;
    while(!q.empty()){
        int x = q.front();q.pop();
        if(x==m) break;
        go(x);
        int z = x - y[1];
        for(int i=0;i<=9;i++) if(i!=y[1]&&ans[z+i]<0&&check(z+i)) q.push(z+i),ans[z+i]=ans[x]+1;
        z = x - y[2]*10;
        for(int i=0;i<=9;i++) if(i!=y[2]&&ans[z+i*10]<0&&check(z+i*10)) q.push(z+i*10),ans[z+i*10]=ans[x]+1;
        z = x - y[3]*100;
        for(int i=0;i<=9;i++) if(i!=y[3]&&ans[z+i*100]<0&&check(z+i*100)) q.push(z+i*100),ans[z+i*100]=ans[x]+1;
        z = x - y[4]*1000;
        for(int i=1;i<=9;i++) if(i!=y[4]&&ans[z+i*1000]<0&&check(z+i*1000)) q.push(z+i*1000),ans[z+i*1000]=ans[x]+1;
    }
    while(!q.empty()) q.pop();
}

int main()
{
    int _;cin>>_;
    while(_--){
        cin>>n>>m;
        dfs();
        if(ans[m]>=0) cout<endl;
        else cout<<"Impossible"<<endl;
    }
    return 0;
}
#include 
#include 
#include 
#include 

using namespace std;

const int M = 1e5;

int ans;
bool ip[M+5];
int dp[M+5];

void isPrime(int n){
    memset(ip,true,sizeof ip);ip[0] = false,ip[1] = false;
    double db = n;
    int m = floor(sqrt(db));
    for(int i = 2;i<=m;i++) if(ip[i])
        for(int j = i;j*i <=n; j++) ip[j*i] = false;
}

void init(){
    ans = 0;
    memset(dp,-1,sizeof dp);
}

int bfs(int a,int b){
    queue<int> q;
    q.push(a);dp[a] = 0;
    while(!q.empty()){
        int p = q.front();q.pop();
        if(p == b) return dp[b];
        else{
            int x1 = p%10, y1 = p %100, z1 = p%1000;
            int x = p - x1, y = p - y1 + x1 , z = p - z1 + y1 ;
            for(int i=0;i<=9;i++){
                int h = x+i;if(dp[h]==-1&&ip[h]) dp[h] = dp[p] + 1,q.push(h);
                h = y+i*10;if(dp[h]==-1&&ip[h]) dp[h] = dp[p] + 1,q.push(h);
                h = z+i*100;if(dp[h]==-1&&ip[h]) dp[h] = dp[p] + 1,q.push(h);
                if(i==0) continue;
                h = z1 + i*1000;if(dp[h]==-1&&ip[h]) dp[h] = dp[p] + 1,q.push(h);
            }
        }
    }
    return dp[b];
}

int main()
{
    int _;cin>>_;
    isPrime(M);
    while(_--){
        init();
        int a,b;cin>>a>>b;
        cout<endl;
    }
    return 0;
}

　　质数单个求就是直接从2到sqrt（n）进行求余

bool check(int x){
    for(int i=2;i*i<=x;i++) if(x%i==0) return false;
    return true;
}

　　筛选方法的话：就是从2到sqrt（n）取i，范围（最大到n），然后进行向后乘i

void isPrime(int n){
    memset(ip,true,sizeof ip);ip[0] = false,ip[1] = false;
    double db = n;
    int m = floor(sqrt(db));
    for(int i = 2;i<=m;i++) if(ip[i])
        for(int j = i;j*i <=n; j++) ip[j*i] = false;
}

POJ - 3087 

sf：简单模拟题 用到 set 进行排除string重复，然后使用string的assign函数进行取子串，

#include 
#include <set>

using namespace std;

int x,cnt,tt,y=1;
string a,b,c,d;
set<string> s;

void slove(){
    s.clear();cnt = 0;
    cin>>x>>a>>b>>c;
    d=c;
    while(1){
        tt = 0;
        for(int i=0;i;
        if(d==c) {cout<" "<break;}
        if(s.count(d)==1) {cout<" -1"<break;}
        a.assign(d,0,x);
        b.assign(d,x,x);
        s.insert(d);
    }
}

int main()
{
    int _;cin>>_;
    while(_--){
        slove();
    }
    return 0;
}

POJ - 3414 

sf：bfs  难点在于 两个水杯容量x，y 与得水量z的关系   z必须能除掉 gcd（x,y）;

gcd函数，switch函数都是优美代码

int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}
#include 
#include 
#include <string.h>
#include 
#include 

using namespace std;

int a,b,c;
bool vis[101][101];

struct node{
    int x,y,num;
}k;

struct mm{
    int number,pre;
}akb[12000];

int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}

void show(int x){
    if(akb[x].pre==-1) return ;
    show(akb[x].pre);
    switch(akb[x].number){
        case 1:puts("FILL(1)");break;
        case 2:puts("FILL(2)");break;
        case 3:puts("POUR(1,2)");break;
        case 4:puts("POUR(2,1)");break;
        case 5:puts("DROP(1)");break;
        case 6:puts("DROP(2)");
    }
}

void bfs(){
    k.x = 0 , k.y = 0 , k.num = 0;
    akb[0].pre = -1;
    vis[0][0]=true;
    queue q;
    q.push(k);
    while(!q.empty()){
        node o = q.front();q.pop();
        int x , y ,num;
        for(int i=1;i<=6;i++){
            if(i==5) x = 0 , y = o.y ;
            else if(i==6) x = o.x , y = 0;
            else if(i==1) x = a , y = o.y;
            else if(i==2) x = o.x , y = b;
            else if(i==3){
                x = o.x - min(o.x , b - o.y);
                y = o.y + min(o.x , b - o.y);
            }
            else{
                x = o.x + min(o.y , a - o.x);
                y = o.y - min(o.y , a - o.x);
            }
            if(vis[x][y]) continue;
            vis[x][y]=true;
            num = o.num + 1;
            akb[x*101+y].number = i;
            akb[x*101+y].pre = o.x*101 + o.y;

            if(x == c || y == c) {cout<101+y);return;}

            node f;f.x=x,f.y=y,f.num=num;
            q.push(f);
        }
    }
}

int main()
{
    cin>>a>>b>>c;
    memset(vis,false,sizeof vis);
    if(c%gcd(a,b)) puts("impossible");
    else bfs();
    return 0;
}

FZU - 2150 

sf：暴力枚举两个草点开始烧 易错点：在于可以同地方烧

#include 
#include 
#include 

using namespace std;

int n,m,ans,cao,step=1;
bool cp[15][15],fk[15][15];
int xx[] = {1,0,0,-1};
int yy[] = {0,1,-1,0};

struct node{
    int x,y,z;
};
node k1,k2;

void show(){
    for(int i=0;i){
        for(int j=0;j)
            cout<" ";cout<<endl;}
}
void show2(){
    for(int i=0;i){
        for(int j=0;j)
            cout<" ";cout<<endl;}
}

void init(){
    memset(fk,false,sizeof fk);
    ans = -1 , cao = 0 ;
    cin>>n>>m;
    for(int i=0;i)
        for(int j=0;j)
    {
        char ch = getchar();
        if(ch == '\n') ch = getchar();
        if(ch == '#') cao++,fk[i][j] = true;
    }
    //show();
}

bool check(int x,int y){
    return x>=0&&x=0&&yfk[x][y];
}

void slove(int a,int b,int c,int d){
    memset(cp,true,sizeof cp);
    k1.x = a,k1.y = b,k1.z= 0; cp[a][b] = false;
    k2.x = c,k2.y = d,k2.z= 0; cp[c][d] = false;
    int cc = 2,cnt = 0;
    queue q;q.push(k1);q.push(k2);
    while(!q.empty()){
        node p = q.front();q.pop();
        int x = p.x, y = p.y,z = p.z;
        //cout<
        for(int i=0;i<4;i++) if(check(x+xx[i],y+yy[i])){
            p.x = x+xx[i], p.y = y+yy[i] , p.z = z + 1;q.push(p);
            cp[p.x][p.y] = false;cnt = p.z;cc++;
        }
    }
    //cout<//show2();
    if(cc == cao) ans = (ans==-1)? cnt : min(cnt,ans);
}

int main()
{
    int _;cin>>_;
    while(_--){
        init();
        if(cao==1) {cout<<"Case "<": "<<0<continue;}
        for(int a=0;a)
            for(int b=0;b)
        {
            if(!fk[a][b]) continue;
            for(int c=a;c)
                for(int d=(c==a)?b+1:0;d)
            {
                //show();
                if(!fk[c][d]) continue;
                //cout<
                slove(a,b,c,d);
            }
        }
        cout<<"Case "<": "<endl;
    }
    return 0;
}

//优化 就是 可以用vector存储草坐标
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int inf = 1e9;

int c[4]={1,0,-1,0};
int d[4]={0,1,0,-1};
int n,m;
string s;
bool vis[20][20];
bool akb[20][20];
struct node{
    int x,y,num;
}e;
vector v;

bool ok(int x,int y){
    if(x<0||x>n||y<0||y>m) return false;
    return true;
}

bool check(){
    for(int i = 0;i < v.size();i ++){
        e = v[i];
        int x = e.x , y = e.y;
        if(!vis[x][y]) return false;
    }
    return true;
}

int bfs(node a,node b){
    memset(vis , false , sizeof vis);
    queue q;
    int h;
    a.num = 0 , b.num = 0;
    q.push(a);q.push(b);
    vis[a.x][a.y] = true;vis[b.x][b.y] = true;
    while(!q.empty()){
        e = q.front();q.pop();
        int x  , y ;
        h = e.num;
        node w;
        for(int i= 0;i < 4;i++){
            x = e.x + c[i] , y = e.y + d[i];
            if(ok(x ,y)&&!vis[x][y]&&akb[x][y]){
                w.x = x , w.y = y;
                w.num = e.num + 1;
                vis[x][y]= true;
                q.push(w);
            }
        }
    }
    return h;
}

int main()
{
    int o = 1;int _;cin>>_;
    while(_--){

        memset(akb , false , sizeof akb);
        cin>>n>>m;
        v.clear();
        for(int i=0;i){
            cin>>s;
            for(int j=0;j)
            if(s[j]=='#'){
                akb[i][j]=true;
                e.x = i , e.y = j;
                v.push_back(e);
            }
        }

        int minn = inf;
        for(int i = 0;i < v.size();i ++)
            for(int j = i;j < v.size();j ++){
                int TnT = bfs(v[i],v[j]);
                if(TnT TnT;
            }

        cout<<"Case "<": ";
        if(minn == inf) cout<<-1<<endl;
        else cout<endl;

    }
    return 0;
}

UVA - 11624 

sf：bfs 火要比人先进队列 易错点在于 开头不止一个火苗

这里使用了struct node 的有参构造

#include 
#include 
#include 
#include <string.h>
#include 

using namespace std;

int n, m , u ,v;
int xx[4] = { 0, -1, 0 ,1 };
int yy[4] = { 1, 0, -1, 0 };
char sm[1005][1005];
struct node{
    int x,y,step,f;
    node(int xx,int yy,int sstep,int ff):x(xx),y(yy),step(sstep),f(ff) {};
};

bool bfs(){
    queue q;
    for(int i=0;i)
        for(int j= 0;j)
            if(sm[i][j]=='F') sm[i][j] = '#' , q.push(node(i , j, 1, 0));
            else if(sm[i][j]=='J') sm[i][j] = '#' , u = i , v = j;
    q.push(node(u , v, 1, 1));
    while(!q.empty()){
        node e = q.front();q.pop();
        int x , y , s , f;x = e.x , y = e.y ,s = e.step , f = e.f;
        //cout<< x << " " << y <<" "<< s << " "<< f<
        if(f == 1&&(x==0||y==0||x==n-1||y==m-1)) {printf("%d\n",s);return true;}
        for(int i = 0;i< 4;i ++){
            int a,b;
            a = x + xx[i] , b = y + yy[i];
            if(a<0||b<0||a>=n||b>=m||sm[a][b]=='#') continue;
            //cout<< a << " " << b <<" "<< s+1 << " "<< f<
            q.push(node(a,b,s+1,f));
            sm[a][b]='#';
        }
    }
    return false;
}

int main()
{
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        for(int i=0;i"%s",sm[i]);
        if(!bfs()) puts("IMPOSSIBLE");
    }
    return 0;
}

POJ - 3984 

sf：简单bfs 必有答案 需要一个前缀记录函数

#include 
#include 

using namespace std;

int prex[5][5];
int prey[5][5];
int w[5][5];
int xx[] = {1,0,0,-1};
int yy[] = {0,1,-1,0};

struct node{
    int x,y;
    node(int xx,int yy): x(xx),y(yy) {};
};

void show(int x,int y){
    if(x==-1) return ;
    show(prex[x][y],prey[x][y]);
    cout<<"("<", "<")"<<endl;
}

int main()
{
    for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>w[i][j];
    prex[0][0] = -1 , prey[0][0] = -1;
    w[0][0] = 1;
    queue q;q.push(node(0,0));
    while(!q.empty()){
        node p = q.front();q.pop();
        int x = p.x, y = p.y;
        for(int i=0;i<4;i++){
            int u = x +xx[i],v = y+yy[i];
            if(u<0||u>=5||v<0||v>=5||w[u][v]==1) continue;
            w[u][v]=1;
            prex[u][v] = x , prey[u][v] = y;
            q.push(node(u,v));
        }
    }
    show(4,4);
    return 0;
}

HDU - 1241 

sf:最小生成树思路 然后遍历 然后dfs

#include 
#include 

using namespace std;

int n,m;
bool cp[101][101];
int xx[] = {1,1,1,0,0,-1,-1,-1};
int yy[] = {1,0,-1,1,-1,1,0,-1};

bool check(int x,int y){
    return x>=0&&x=0&&ycp[x][y];
}

void dfs(int u,int v){
    for(int i=0;i<8;i++){
        int a = u+xx[i] , b = v + yy[i];
        if(check(a,b)){
            cp[a][b] = false;
            dfs(a,b);
        }
    }
}

void show(){
    for(int i=0;i){
        for(int j=0;j" ";cout<<endl;
    }
}

int main()
{
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        //cout<
        memset(cp,false,sizeof cp);
        for(int i=0;ifor(int j=0;j){
            char ch = getchar();//cout<
            while(ch!='@'&&ch!='*') ch = getchar();
            if(ch=='@') cp[i][j] = true;
        }
        //show();
        int ans = 0;
        for(int i=0;ifor(int j=0;jif(cp[i][j]){
            cp[i][j] = false;ans++;dfs(i,j);
        }
        cout<endl;
    }
    return 0;
}

HDU - 1495 

sf：bfs 然后易错点在于 ：必须一个容器为空，

#include 
#include 
#include 

using namespace std;

int x,y,z,cnt;
bool fk[1000005];
struct node{
    int u,v,w,step;
    node(int uu,int vv,int ww,int ss):u(uu),v(vv),w(ww),step(ss) {};
};

int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}

bool bfs(){
    queue q;q.push(node(x,0,0,0));fk[x*10000] = false;
    while(!q.empty()){
        node p = q.front();q.pop();
        int u = p.u , v = p.v , w = p.w,step = p.step;
        //cout<
        if(u == cnt || v == cnt || w == cnt) {
            step = (!u||!v||!w)?step:step+1;
            cout<return true;
        }
        int uu,vv,ww,tnt;
        if(u){
            uu = u+v>=y?u+v-y:0;
            vv = u+v>=y?y:u+v;
            ww = w;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
            uu = u+w>=z?u+w-z:0;
            vv = v;
            ww = u+w>=z?z:u+w;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
        }
        if(v){
            uu = u+v;
            vv = 0;
            ww = w;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
            uu = u;
            vv = v+w>=z?v+w-z:0;
            ww = v+w>=z?z:v+w;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
        }
        if(w){
            uu = u+w;
            vv = v;
            ww = 0;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
            uu = u;
            vv = v+w>=y?y:v+w;
            ww = v+w>=y?v+w-y:0;
            tnt = uu*10000+vv*100+ww;
            if(fk[tnt]){fk[tnt]=false;q.push(node(uu,vv,ww,step+1));}
        }
    }
    return false;
}

int main()
{
    while(cin>>x>>y>>z){
        if(x==0&&y==0&&z==0) break;
        if(x%2) {puts("NO");continue;}
        cnt = x/2;memset(fk,true,sizeof fk);
        if(cnt%gcd(x,gcd(y,z))) {puts("NO");continue;}
        if(!bfs()) puts("NO");
    }
    return 0;
}
#include 
#include 
#include 
#include <string.h>
#include 

using namespace std;

int s, n, m;
bool cp[101][100][100];
struct node{
    int x,y,z,num;
    node(int xx,int yy,int zz,int nn):x(xx),y(yy),z(zz),num(nn) {};
};
node e = node(0,0,0,0);

bool bfs(){
    int tt = s / 2;
    queue q;
    q.push(node(s,0,0,0));
    cp[s][0][0] = true;
    while(!q.empty()){
        int a,b,c,x,y,z;
        e = q.front();q.pop();
        a = e.x , b = e.y , c = e.z;
        //cout<
        if(a == tt|| b == tt || c == tt){
            if(!a||!b||!c) cout<endl;
            else cout<1<<endl;
            return true;
        }
        for(int i=0;i<6;i++){
            if(i==0) if(b==n) continue;else x = a - min(a ,n - b) , y = b + min(a , n - b) , z = c;
            else if(i==1) x = a + b , y = 0 , z = c;
            else if(i==2) if(c==m) continue;else x = a - min(a ,m - c) , y = b , z = c + min(a ,m - c);
            else if(i==3) x = a + c , y = b , z = 0;
            else if(i==4) if(b==n) continue;else x = a , y = b + min(c ,n - b)  , z = c - min(c ,n - b);
            else if(i==5) if(c==m) continue;else x = a , y = b - min( b ,m - c ), z = c + min( b ,m - c );
            if(cp[x][y][z]) continue;cp[x][y][z] = true;
            q.push(node(x,y,z,e.num+1));
        }
    }
    return false;
}

int main()
{
    while(cin>>s>>n>>m&&s){
        if(s%2) {puts("NO");continue;}
        memset(cp,false,sizeof cp);
        if(!bfs()) puts("NO");
    }
    return 0;
}

HDU - 2612 

sf：bfs加上两个记录长度的状态函数（类似求最短路径）

#include 
#include 
#include 
#include 

using namespace std;

const int inf = 1e9;

int n,m;
int xx[4] = {1,0,0,-1};
int yy[4] = {0,-1,1,0};
char mp[205][205];
int a[205][205];
int b[205][205];
int ans;

struct node{
    int x , y , f;
    node(int xx , int yy , int ff):x(xx),y(yy),f(ff) {};
};
node e = node(0,0,0);

int bfs(){
    ans = inf;
    memset(a,-1,sizeof a);
    memset(b,-1,sizeof b);
    queue q;
    for(int i = 0;i)
        for(int j = 0;j)
            if(mp[i][j]=='Y') q.push(node(i , j , 0)) , a[i][j] = 0;
            else if(mp[i][j]=='M') q.push(node(i , j, 1)) , b[i][j] = 0;
    while(!q.empty()){
        int x, y , u, v;
        e = q.front();q.pop();
        x = e.x, y = e.y;
        for(int i=0;i<4;i++){
            u = x + xx[i] , v = y + yy[i];
            if(u<0||v<0||u>=n||v>=m) continue;
            if(mp[u][v]=='#') continue;
            if(e.f==0&&a[u][v]== -1){
                a[u][v] = a[x][y] + 1;
                if(mp[u][v]=='@'&&b[u][v]!=-1&&(a[u][v]+b[u][v] < ans)) ans = a[u][v]+b[u][v];
                q.push(node(u,v,e.f));
            }
            else if(e.f==1&&b[u][v]==-1){
                b[u][v] = b[x][y] + 1;
                if(mp[u][v]=='@'&&a[u][v]!=-1&&(a[u][v]+b[u][v] < ans)) ans = a[u][v]+b[u][v];
                q.push(node(u,v,e.f));
            }
        }

    }
    return ans;
}

int main()
{
    while(cin>>n>>m){
        for(int i=0;i"%s",mp[i]);
        cout<11<<endl;
    }
    return 0;
}
搜索

相关

力扣530题（二叉搜索树的最小绝对差）

快速排序与随机构建二叉搜索树

PyCharm2021使用教程 ---9、PyCharm中的搜索技巧（文件/函数/内容）

广度优先搜索复习笔记

无人机视觉导航搜索资料

find 语句过滤掉某个目录搜索

Linux搜索指定目录中所有文件的内容

二分搜索的变形

MySQL（三）用正则表达式搜索

在 Spring Boot 中使用搜索引擎 Elasticsearch

安卓手机便签模糊搜索历史内容怎么实现？

SpringBoot2.0 整合 ElasticSearch框架,实现高性能搜索引擎

标签