7/23·morning

1248：Dungeon Master  http://ybt.ssoier.cn:8088/problem_show.php?pid=1248

#include<bits/stdc++.h>
using namespace std;
char a[103][103][103];
int vis[103][103][103];
int sx,sy,sz,ex,ey,ez;
struct qwert{
    int x,y,z;
};
int xx[6]={1,-1,0,0,0,0};
int yy[6]={0,0,1,-1,0,0};
int zz[6]={0,0,0,0,1,-1};
void bfs(){
    memset(vis,-1,sizeof(vis));
    queue<qwert> q;
    while(!q.empty())q.pop();
    q.push({sx,sy,sz});
    vis[sx][sy][sz]=0;
    while(!q.empty){
        qwert n=q.front();q.pop();
        for(int i=0;i<6;i++){
            int lx,ly,lz
            if(n.x>0&&n.x<=H&&n.y>0&&n.y<=A&&n.z>0&&n.z<=B&&vis[n.x][n.y][n.z]!=-1]){
                q.push()
            }
        }
    }
}
int main(){
    int H,A,B;
    while(H!=0&&A!=0&&B!=0){
        cin>>H>>A>>B;
        for(int i=1;i<=H;i++){
            for(int j=1;j<=A;j++){
                for(int k=1;k<=B;k++){
                    cin>>a[i][j][k];
                    if(a[i][j][k]=='S'){
                        sx=i;sy=j;sz=k;
                    }
                    if(a[i][j][k]=='E'){
                        ex=i;ey=j;ez=k;
                    }
                }
            }
        }
        bfs();
    }
    return 0;
}
//未完成

问题 A: 魔法鲜花  http://www.jzoj.cn/problem.php?cid=5707&pid=0

# include <bits/stdc++.h>
using namespace std;
const int maxN=1e5+1;
struct node{
    int wz,step;
};
string ABC="DABC";
int n,k;
queue<node>Q;
int vis[2*maxN];
int fa[maxN];int cz[maxN];
void findfa(int w){
    if(w==n){
        return;
    }
    else{
        findfa(fa[w]);
        cout<<ABC[cz[w]];
    }
}
void bfs(int start){
    Q.push({start,0});
    vis[start]=1;
    fa[start]=0;cz[start]='D';
    while (!Q.empty()){
        int touwz=Q.front().wz;
        int toustep=Q.front().step;
        Q.pop();
        
        int newwz[4];
        newwz[1]=touwz+1;
        newwz[2]=touwz-10;
        newwz[3]=touwz*2;
        int newstep=toustep+1;
                
        for (int i=1;i<=3;i++){
            
            if (newwz[i]==k) {
                cout<<newstep<<endl;
                fa[newwz[i]]=touwz;
                cz[newwz[i]]=i;
                findfa(newwz[i]);
                return;
            } 
            else if(vis[newwz[i]]==0 && newwz[i]>0 && newwz[i]<=maxN-1) {
                Q.push({newwz[i],newstep});
                fa[newwz[i]]=touwz;
                cz[newwz[i]]=i;
                vis[newwz[i]]=1;
           }
           
         }
    }
}


int main(){
    cin>>n>>k;
    if (n==k) cout<<0<<endl;
    else bfs(n); 
    return 0;
}

问题 B: 抓住那头牛  http://www.jzoj.cn/problem.php?cid=5707&pid=1

#include <bits/stdc++.h>
#define N 100001
using namespace std;
bool vis[N];
int dir[2]={-1,1};
struct node
{
    int x;
    int step;
}q[N];
void bfs(int n,int k)
{
    int head=1,tail=1;
    vis[n]=1;
    q[tail].x=n;
    q[tail].step=0;
    tail++;
    while(head<tail)
    {
        int x=q[head].x;
        int step=q[head].step;
        if(x==k)
        {
            cout<<step<<endl;
            break;
        }
        for(int i=0;i<2;i++)
        {
            int nx=x+dir[i];
            if(1<=nx and nx<=N and vis[nx]==0)
            {
                vis[nx]=1;
                q[tail].x=nx;
                q[tail].step=step+1;
                tail++;
            }
        }
        int nx=2*x;
        if(1<=nx and nx<=N and vis[nx]==0)
        {
            vis[nx]=1;
            q[tail].x=nx;
            q[tail].step=step+1;
            tail++;
        }
        head++;
    }
}
int main()
{
    int n,k;
    cin>>n>>k;
    if(k<n)
    {
        cout<<n-k<<endl;
    } 
    else
    {
        bfs(n,k);
    }
    return 0;
}

问题 C: 【提高】魔板  http://www.jzoj.cn/problem.php?cid=5707&pid=2

#include<bits/stdc++.h>
using namespace std;
string start;
struct node{
    string zt,cz;
};
set<string> vis;
string ABC="DABC";
string change(string str,char abc){
    string cstr="";
    /*
    0 1 2 3
    4 5 6 7
    A
    4 5 6 7
    0 1 2 3
    B
    3 0 1 2
    7 4 5 6
    C
    0 5 1 3
    4 6 2 7
    */
    if(abc=='A'){
        cstr+=str[4];cstr+=str[5];
        cstr+=str[6];cstr+=str[7];
        cstr+=str[0];cstr+=str[1];
        cstr+=str[2];cstr+=str[3];
    }
    else if(abc=='B'){
        cstr+=str[3];cstr+=str[0];
        cstr+=str[1];cstr+=str[2];
        cstr+=str[7];cstr+=str[4];
        cstr+=str[5];cstr+=str[6];
    }
    else if(abc=='C'){
        cstr+=str[0];cstr+=str[5];
        cstr+=str[1];cstr+=str[3];
        cstr+=str[4];cstr+=str[6];
        cstr+=str[2];cstr+=str[7];
    }
    return cstr;
} 
void bfs(){
    queue<node> q;
    while(!q.empty())q.pop();
    q.push({start,""});
    vis.insert(start);
    while(!q.empty()){
        string nowzt=q.front().zt,nowcz=q.front().cz;q.pop();
        //cout<<nowzt<<endl;
        for(int i=1;i<=3;i++){
            string newstr=change(nowzt,ABC[i]);
            string newcz=nowcz+ABC[i];
            if(newstr=="12345678"){
                cout<<newcz;
                exit(0);
            }
            if(vis.count(newstr)==0){
                q.push({newstr,newcz});
                vis.insert(newstr);
            }
        }
    }
}
int main(){
    int xx;start="";
    for(int i=1;i<=8;i++){
        cin>>xx;
        start+=char(xx+48);
    }
    bfs(); 
    cout<<"wujie"<<endl; 
    return 0;
}

问题 D: 连通块  http://www.jzoj.cn/problem.php?cid=5707&pid=3

#include<bits/stdc++.h>
using namespace std;
struct pos{
    int x,y;
};
int n,m;
int a[203][203];
bool vis[203][203];
int tx[4]={1,0,-1,0};
int ty[4]={0,1,0,-1};
void bfs(int bx,int by){
    queue<pos> q;
    while(!q.empty())q.pop();
    vis[bx][by]=1;
    q.push({bx,by});
    while(!q.empty()){
        pos c=q.front();q.pop();
        for(int i=0;i<4;i++){
            int nx=c.x+tx[i];
            int ny=c.y+ty[i];
            if(nx>0&&nx<=n&&ny>0&&ny<=m&&!vis[nx][ny]&&a[nx][ny]!=0){
                vis[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j]&&a[i][j]!=0){
                bfs(i,j);
                sum++;
            }
        }
    }
    cout<<sum;
    return 0;
}