p1432-倒水问题

wflengxuenong · 2024-05-23 14:44:08 · 个人记录

题解里面写的都太啰嗦了，要利用函数来处理重复问题

#include<bits/stdc++.h>  
using namespace std;
const int N=1000009;
char qz[N];
int qy[N],qx[N],qf[N],step1[N],head=0,tail=0,pas[N];
bool v[1009][1009];

int x,y,z,flag=0;
void inser(int tx,int ty,int step2,char cz,int fa) {
    if(tx<0||ty<0||tx>x||ty>y)return;
    if(v[tx][ty])return;
    tail++;
    qx[tail]=tx,qy[tail]=ty,qz[tail]=cz,qf[tail]=fa;
    step1[tail]=step2;
    v[tx][ty]=1;
}
void bfs(){
    memset(v,0,sizeof(v));
    cin>>x>>y>>z;
    int cx,cy,step3;
    head=0;
    tail=0;flag=0;
    while(head<=tail) {
        cx=qx[head];
        cy=qy[head];
        step3=step1[head];

        v[cx][cy]=1;
        if(cy==z) {
            cout<<step3<<" ";
            flag=head;
            for(int j=step3;j>0;j--)
                pas[j]=flag,flag=qf[flag];
            for(int j=1;j<=step3;j++)
                printf("%c ",qz[pas[j]]);
            cout<<endl;
            break;
        }
        inser(x,cy,step3+1,'1',head);
        inser(0,cy,step3+1,'3',head);
        inser(cx,y,step3+1,'2',head);
        inser(cx,0,step3+1,'4',head);
        inser(0,cy+cx,step3+1,'6',head);
        inser(cx-y+cy,y,step3+1,'6',head);
        inser(cx+cy,0,step3+1,'5',head);
        inser(x,cy-x+cx,step3+1,'5',head);
        head++;
    }

}
int main() 
{
    int t;
    cin>>t;
    while(t--)
        bfs();

    return 0;
}