前言

🔗Vjudge题集链接(组员可进)🔗
很多讲的不是很清楚或者没理解的建议拿着纸笔🖊照着代码演算一遍,这样对代码思想和算法原理的理解有很大帮助,然后一些
常用的模板(bfs,素数表)是要背下来的(理解了更好).
另,C++比C方便很多,而且C有的C++也有,C没有的C++也有,建议使用C++作为算法学习主要语言…

知识预备

🔗【中文wiki】深度优先搜索(需要特殊上网手段)🔗
🔗【算法入门】深度优先搜索(DFS)🔗
🔗算法图解之广度优先算法BFS🔗
🔗【算法入门】广度/宽度优先搜索(BFS)🔗
🔗谷歌访问助手,远离百度,从我做起🔗

正文

A：Dungeon Master (poj-2251)

题意:
三维迷宫,给定出口和入口,要求输出最短路径长度.

思路:
bfs求解,只需要在二维的基础上加一维(上下两个方向)即可.

知识点:
🔗 bfs 🔗
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

char m[31][31][31];
bool v[31][31][31];
int L,R,C;
int start_x=0,start_y=0,start_z=0,end_x=0,end_y=0,end_z=0;//起终点坐标
int dir[6][3]= {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}}; //上下东南西北

struct node
{
    int x,y,z;//坐标
    int step;//步数
};



void bfs()
{
    queue<node> S;
    struct node st;
    st.step=0;
    st.x=start_x;
    st.y=start_y;
    st.z=start_z;
    S.push(st);
    v[st.x][st.y][st.z]=true;

    while(!S.empty())
    {
        struct node tmp=S.front();
        S.pop();
        if(tmp.x==end_x&&tmp.y==end_y&&tmp.z==end_z)
        {
            cout<<"Escaped in "<<tmp.step<<" minute(s)."<<endl;
            return;
        }
        struct node tmp2;
        up(6)
        {
            tmp2.x=tmp.x+dir[i][0];
            tmp2.y=tmp.y+dir[i][1];
            tmp2.z=tmp.z+dir[i][2];
            tmp2.step=tmp.step+1;
            if(tmp2.x<0||tmp2.x>=L||tmp2.y<0||tmp2.y>=R||tmp2.z<0||tmp2.z>=C)
                continue;
            else if(m[tmp2.x][tmp2.y][tmp2.z]=='#'||v[tmp2.x][tmp2.y][tmp2.z])
                continue;
            else
            {
                v[tmp2.x][tmp2.y][tmp2.z]=true;
                S.push(tmp2);
            }
        }
    }
    cout<<"Trapped!"<<endl;
    return ;
}


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    while(cin>>L>>R>>C)
    {
        if(!(L||R||C))
            break;
        memset(v,false,sizeof(v));
        up(L)
        for(int j=0; j<R; j++)
            for(int k=0; k<C; k++)
            {
                cin>>m[i][j][k];
                if(m[i][j][k]=='S')
                    start_x=i,start_y=j,start_z=k;
                else if(m[i][j][k]=='E')
                    end_x=i,end_y=j,end_z=k;
            }
        bfs();
    }
    return 0;
}

B：Catch That Cow (poj-3278)

题意:
给定牛🐂和人在直线上的坐标,人可以沿着直线左右移动一个单位,或者传送到2*X的位置(设X是人的坐标),耗费时间都是1mins.求人抓到牛🐂的时间.

思路:
看到题的瞬间就想到了动态规划,然而这是搜索专题,就都讲下吧.

动态规划: 我是图
动态规划思想见知识点链接,这里直接上思路.给出一个数组dp,dp[i]表示从起点到i的时间(或者直接说步数),给0到牛坐标初始化一个数值为i到起点坐标的绝对值(即起点到i的最长步数).
考虑直线上任意一点p:

  • p点本身
  • p+1点的最优+1
  • p-1点的最优+1
  • p/2点的最优+1(p为偶数)

对于奇数,考虑前3个.p+1的最优只能是dp[i+1]，此时还没有发生变化,和dp[(i+1)/2]+1,简单理解就是偶数数尽量使用传送,我自己推导的时候遇到了数学难题,能力不够无法证明,所以这里就当贪心算法了,我记得我学长给我讲的时候就说的是贪心.
又由于dp[i+1]=dp[i]+1，所以不再考虑dp[i+1]。同时，也不考虑dp[p/2]+1.
对于偶数多考虑一个dp[p/2]+1.

BFS:
套模板:

  1. 初始化,标记初始点已访问并将初始点入队列
  2. 循环
    1. 标记此处,已经遍历过
    2. 判断是否退出,是则return
    3. 操作当前数
    4. 判断越界和是否已经遍历过
    5. push
  3. return

知识点:🔗动态规划🔗
贪心: 我觉得、我认为,找规律就vans了.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

int dp[100007];


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    int n,k;
    while(cin>>n>>k){
        memset(dp,0,sizeof(dp));

        up(k+1){ //初始化
        dp[i]=abs(n-i);
        }

        for(int i=n+1;i<=k;i++){
            if(i&1){
                dp[i]=min(dp[i],dp[(i+1)/2]+2);
                dp[i]=min(dp[i],dp[i-1]+1);
            }
            else {
                dp[i]=min(dp[i],dp[i/2]+1);
                dp[i]=min(dp[i],dp[i-1]+1);
                dp[i]=min(dp[(i+1)/2]+2,dp[i]);

            }
        }
        for(int i=n+1;i<=k;i++)cout<<dp[i]<<endl;
       // cout<<dp[k]<<endl;
    }
    return 0;
}

网上扒的bfs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;

struct node{
    int  pos;
    int  ct;
    node(int p,int ctt):pos(p),ct(ctt){}
};

bool view[100000+5]={false};
int bfs(int n,int k){
    queue <node> q;
    q.push(node(n,0));
    while(!q.empty()){
        struct node u=q.front();
        q.pop();
        int p=u.pos;
        view[p]=true;
        if(p<0||p>100000) continue;
        if(p==k){
            return u.ct;
        }
        if(p<100001&&!view[p+1]){
            q.push(node(p+1,u.ct+1));
        }
        if(p>0&&!view[p-1]){
            q.push(node(p-1,u.ct+1));
        }
        if(p<50001&&!view[p*2]){
            q.push(node(2*p,u.ct+1));
        }
    }
    return -1;
}

int main(void){
    int N,K;
    scanf("%d %d",&N,&K);
    printf("%d",bfs(N,K));
}

C：Find The Multiple (poj-1426)

题意:
给个数n,找到一个只由0|1组成的并且可以被n整除的数

思路:
🔗广搜bfs🔗
🔗深搜dfs🔗

代码:
见思路链接

D：Prime Path (poj-3126)

题意:
给出n和m两个4位的素数,现在变换n的任何一位数字,但变换后依旧要是素数,要求从n变到m的最少步数

思路:
如果是最大步数直接打素数表遍历就好,但既然是最少…
打出素数表后,通过改变操作数的每一位进行bfs;

  1. 打素数表(套模板)
  2. 初始化
  3. 标记初始点并入队列
  4. 循环
    1. 判断是否到达终点,是则return
    2. 切割各个位
    3. 对各个位分别改变并判断是否满足条件(素数),满足入队列push
  5. return

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

const int maxn=10007;
int pri[maxn],a[maxn],vis[maxn];
int n,m,p=0;

struct node
{
    int val;
    int step;
};

void getp()//素数表
{
    int tot=0;
    for (int i=2; i<=maxn; i++)
    {
        if(!vis[i])
        {
            a[tot++]=i;
            for(int j=2*i; j<=maxn; j+=i)
                vis[j]=1;
        }
    }
    for (int i=0; i<tot; i++) //取出4位数的素数
    {
        if(a[i]>1000&&a[i]<10000)
            pri[p++]=a[i];
    }
}

bool dif(int l,int r)//判断数是否差一位
{
    int sum=0;
    while(l!=0)
    {
        int tmp1=l%10;
        int tmp2=r%10;
        if (tmp1!=tmp2)
            sum++;
        l/=10;
        r/=10;
    }
    if(sum==1)
        return true;
    else
        return false;
}

void bfs()//模板
{
    queue<node> Q;
    //Q.push({n,0});
    //VJ的编译器不允许这样写...
    struct node t;
    t.step=0;
    t.val=n;
    Q.push(t);

    vis[n]=1;
    while(!Q.empty())
    {
        struct node tmp=Q.front();
        Q.pop();
        if(tmp.val==m)
        {
            cout<<tmp.step<<endl;
            return ;
        }
        up(p)
        {
            if(!vis[pri[i]]&&dif(pri[i],tmp.val))
            {
                vis[pri[i]]=1;
               // Q.push({pri[i],tmp.step+1});
               t.val=pri[i];
               t.step=tmp.step+1;
               Q.push(t);
            }
        }

    }
    cout<<"Impossible"<<endl;
    return ;
}


int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        getp();
        memset(vis,0,sizeof(vis));//vis曾用于标记素数表,故需要初始化
        bfs();
    }

    return 0;
}

E：迷宫问题 (poj-3984)

题意:
二维迷宫找最短路径(输出路线)

思路:
在迷宫问题最短路径的基础上记录下路径即可:🔗外部链接🔗
代码: 见思路🔗外部链接🔗

F：Oil Deposits (poj-1241)

题意:
二维字符数组’@‘表示有油,’*'无油,相邻(包括对角线)则属于同一油田,问有多少个油田

思路:
水题,深搜,19级上套题就有

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
char mp[107][107];
bool v[107][107];
int dir[8][2]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int m=0,n=0;

int dfs(int sx,int sy)
{
    if(v[sx][sy]||mp[sx][sy]=='*')
        return 0;
    v[sx][sy]=true;
    //cout<<sx<<"-"<<sy<<endl;
    up(8)
    {
        int tmp_x=sx+dir[i][0];
        int tmp_y=sy+dir[i][1];
        if(tmp_x<0||tmp_x>=m||tmp_y<0||tmp_y>=n||v[tmp_x][tmp_y]||mp[tmp_x][tmp_y]=='*');
        else
            dfs(tmp_x,tmp_y);
    }
    return 1;
}


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    while(cin>>m>>n)
    {
        if(!(m|n))break;
        memset(v,false,sizeof(v));
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {

                cin>>mp[i][j];
            }
        }
        int sum=0;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
               // cout<<dfs(i,j)<<endl;
                sum+=dfs(i,j);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

G：非常可乐 (hdu-1495)

题意:

我是图

思路:
注意装可乐的瓶子也是可以用的,6个选择:

  • S <-> N
  • S <-> M
  • N <-> M

用bfs解决;
也有数学方法解决(数论): 🔗外部链接🔗

我是图

直接扒代码🔗外部连接🔗:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100+5
using namespace std;
 
struct node{
    int a,b,s,t;
}cole[N],st;
 
int a,b,s;
int vis[N][N];  //记录状态（二维就可以记录三维的状态）。
int bfs()
{
    queue<node> q;
    memset(vis,0,sizeof(vis));
    st.a=0; st.b=0; st.s=s; st.t=0;
    q.push(st);
    vis[a][b]=1;
    while(!q.empty())
    {
        node u=q.front(),v;
        //能平分的条件是可乐瓶和容量大（a）的杯子都装着最开始一半的可乐。
        if(u.a==s/2 && u.s==s/2)
            return u.t;
        if(u.s && u.a!=a)   //s->a
        {
            int c=a-u.a;
            if(u.s>=c) v.a=a,v.s=u.s-c;
            else v.a=u.a+u.s,v.s=0;
            v.b=u.b; v.t=u.t+1;
            if(!vis[v.a][v.b])  //只从之前没有出现的状态往下推，下同。
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        if(u.s && u.b!=b)   //s->b
        {
            int c=b-u.b;
            if(u.s>=c) v.b=b,v.s=u.s-c;
            else v.b=u.b+u.s,v.s=0;
            v.a=u.a; v.t=u.t+1;
            if(!vis[v.a][v.b])
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        if(u.a && u.s!=s)   //a->s
        {
            int c=s-u.s;
            if(u.a>=c) v.s=s,v.a=u.a-c;
            else v.s=u.s+u.a,v.a=0;
            v.b=u.b; v.t=u.t+1;
            if(!vis[v.a][v.b])
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        if(u.a && u.b!=b)   //a->b
        {
            int c=b-u.b;
            if(u.a>=c) v.b=b,v.a=u.a-c;
            else v.b=u.b+u.a,v.a=0;
            v.s=u.s; v.t=u.t+1;
            if(!vis[v.a][v.b])
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        if(u.b && u.a!=a)   //b->s
        {
            int c=a-u.a;
            if(u.b>=c) v.a=a,v.b=u.b-c;
            else v.a=u.a+u.b,v.b=0;
            v.s=u.s; v.t=u.t+1;
            if(!vis[v.a][v.b])
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        if(u.b && u.s!=s)   //b->a
        {
            int c=s-u.s;
            if(u.b>=c) v.s=s,v.b=u.b-c;
            else v.s=u.s+u.b,v.b=0;
            v.a=u.a; v.t=u.t+1;
            if(!vis[v.a][v.b])
            {
                q.push(v);
                vis[v.a][v.b]=1;
            }
        }
        q.pop();
    }
    return 0;   //所有扩展的状态都不能使之平分。
}
int main()
{
    while(scanf("%d%d%d",&s,&a,&b),s||a||b)
    {
        if(s%2)
        {
            puts("NO");
            continue;
        }
        if(a<b) swap(a,b); //这里使a作大号杯，方便bfs条件的判定。
        int ans=bfs();
        if(ans) printf("%d\n",ans);
        else puts("NO");
    }
    return 0;
}

H：Find a way (hdu-2612)

题意:
Y和M两人到达同一个肯德基’@'的最短路径.

思路:
对Y和M分别进行2次bfs,因为最短路径需要合计,所以分别进行bfs时不设置终止条件(即找到每个kfc的路径).
对Y进行bfs得到Y到每个kfc的最短距离并保存,然后对M进行bfs得到M到每个kfc的最短距离加上前面Y的距离即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433


char ma[MAXN][MAXN];//存图
int n, m;//图的大小
int v[MAXN][MAXN];//标记数组
struct node
{
    int x, y, step;//x坐标,y坐标，及到达此点的步数
}t, p, q, que[121212];
int ans[MAXN][MAXN];//记录到达@点的步数
int vectors[][2] = {1, 0, -1, 0, 0, 1, 0, -1};//上下左右四个方向
void bfs(int x, int y)
{
    v[x][y] = 1;//标记
    int front = 0, rear = 0;
    p.x = x;
    p.y = y;
    p.step = 0;
    que[rear++] = p;//入队
    while(front<rear)
    {
        q = que[front++];
        for(int i=0;i<4;i++)//四个方向遍历
         {
            p.x = q.x + vectors[i][0];
            p.y = q.y + vectors[i][1];
            if(p.x<0||p.x>=n||p.y<0||p.y>=m||v[p.x][p.y]||ma[p.x][p.y]=='#')
                 continue;//不符条件
            if(ma[p.x][p.y]=='@')//如果是终点
            {
                ans[p.x][p.y] += q.step + 1;//记录步数
            }
            v[p.x][p.y] = 1;//标记
            p.step = q.step+1;//更新步数
            que[rear++] = p;//入队
            }
    }
    return ;
}
int main()
{

    while(~scanf("%d %d", &n, &m))
    {
    memset(ans, 0, sizeof(ans));//清零
    for(int i=0;i<n;i++)
        scanf("%s", ma[i]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(ma[i][j]=='Y')
            {
                t.x = i;//记录横坐标
                t.y = j;//记录竖坐标
                t.step = 0;
            }
        }
    }
    memset(v, 0, sizeof(v));
    bfs(t.x, t.y);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(ma[i][j]=='M')
            {
                t.x = i;
                t.y = j;
                t.step = 0;
            }
        }
    }
    memset(v, 0, sizeof(v));//记得清零
    bfs(t.x, t.y);
    int min = 989898;//定义一个大一点的数
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
              if(ans[i][j]<min&&ans[i][j])
                    min = ans[i][j];
        }
    }
    printf("%d\n", min*11);//别忘了*11
    }
    return 0;
}


I：胜利大逃亡 (hdu-1253)

题意:
不会吧? 不会吧? 不会真有人看不懂中文吧?

思路:
3维bfs,直接抄我以前写的代码了,毕竟刚学的时候写的,某些代码习惯不要学.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <queue>
#include <stdio.h>
#include <cstring>
#include <stdlib.h>
using namespace std;
int x,y,z,t;
int a[52][52][52];
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int b[52][52][52];
struct Node
{
    int x,y,z;
    int step;
};

void bfs()
{
    queue<Node> Q;
    int xi=0,yi=0,zi=0,step=0;
    b[0][0][0]=1;
    Q.push({xi,yi,zi,step});

    while(!Q.empty())
    {
        Node tmp=Q.front();
        Q.pop();
        xi=tmp.x;
        yi=tmp.y;
        zi=tmp.z;
        step=tmp.step;

        //printf("%d: (%d, %d, %d)\n",step,xi,zi,zi);
        if(xi==x-1&&yi==y-1&&zi==z-1)
        {
            if(step<=t)cout<<step<<endl;
            else cout<<-1<<endl;
            return;
        }
        for(int i=0; i<6; i++)
        {

             int xj=xi+dir[i][0];
             int yj=yi+dir[i][1];
             int zj=zi+dir[i][2];
             int sj=step+1;
            //printf("%d: (%d, %d, %d)\n",step,xj,yj,zj);
            if(xj<0||xj>=x||yj<0||yj>=y||zj<0||zj>=z){
                    //cout<<"fail"<<endl;
                    continue;
            }
           // cout<<Q.size()<<":::"<<a[xj][yj][zj]<<" "<<b[xi][yi][zi]<<endl;
            if(a[xj][yj][zj]!=1&&!b[xj][yj][zj]){
               // cout<<"success"<<endl;
                Q.push({xj,yj,zj,sj});
                b[xj][yj][zj]=1;
            }
        }
    }
    cout<<-1<<endl;
}
int main()
{
    int k;
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d %d %d %d",&x,&y,&z,&t);
        for(int i=0; i<x; i++)
        {
            for(int j=0; j<y; j++)
            {
                for(int l=0; l<z; l++)
                {
                    scanf("%1d",&a[i][j][l]);
                }
            }
        }
        memset(b,0,sizeof(b));
        bfs();
    }

    return 0;
}

J：胜利大逃亡(续) (hdu-1429)

题意:
…

思路:
以前混过去的,果然该还的还是要还的…
状态压缩+bfs
每个点有一个钥匙🔑的状态由一个10位二进制数表示,第i位为1则表示第i把钥匙🔑已经到手,遇到门直接用位运算匹配钥匙🔑的值即可

知识点:
🔗逼乎🔗
🔗CSDN🔗
位运算(百度)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

using namespace std;

int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
char a[22][22];//地图
int v[22][22][2<<10];//一个点可以多次经过,但他们所具有的钥匙状态不同,若钥匙状态相同说明重复了,不可继续访问该点.
int m,n,t,key;

struct Node
{
    int x,y;
    int step;
    int key;//钥匙状态,一个二进制数
}S;

void bfs(){
queue<Node> Q;
Q.push({S.x,S.y,0,0});
v[S.x][S.y][0]=1;
while(!Q.empty()){
    Node now=Q.front(),next;
    Q.pop();
    for(int i=0;i<4;i++){
        next=now;
        next.x+=dir[i][0];
        next.y+=dir[i][1];
        next.step++;
        if(next.step>=t||next.x<0||next.x>=m||next.y<0||next.y>=n||v[next.x][next.y][next.key])continue;//超时超界以及钥匙状态判断
        if(a[next.x][next.y]=='^'){ //终点,结束.
            cout<<next.step<<endl;
            return ;
        }
        else if(a[next.x][next.y]=='*')continue; //墙
        else if(a[next.x][next.y]>='A'&&a[next.x][next.y]<='Z'){ //遇到门
            if(next.key>>(a[next.x][next.y]-'A') &1){
                v[next.x][next.y][next.key]=1;
                Q.push(next);            }
        }
        else if(a[next.x][next.y]>='a'&&a[next.x][next.y]<='z'){ //遇到钥匙
            next.key|=(1<<(a[next.x][next.y]-'A'));
            v[next.x][next.y][next.key]=1;
            Q.push(next);
        }
        else { //普通的路
            v[next.x][next.y][next.key]=1;
            Q.push(next);
        }
    }
}
cout<<-1<<endl; //bfs失败,无法逃脱
return ;
}

int main()
{
    while(cin>>m>>n>>t){
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
                if(a[i][j]=='@'){
                    S.x=i;
                    S.y=j;
                }
            }
        }
        memset(v,0,sizeof(v));//初始化
        bfs();
    }

    return 0;
}

K：诡异的楼梯 (hdu-1180)

题意:
…

思路:
bfs,bfs,bfs,全是bfs…
注意楼梯是捷径,如果你走的方向恰好和楼梯一样,你就可以通过楼梯,人的方向由dir可以顺便得出
🔗详细一点的讲解🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int sx,sy,m,n,ans;
char a[20][20],ch;
bool vis[20][20];
int dir[4][2]= {1,0, 0,1, -1,0, 0,-1}; //下右上左
struct node
{
    int x,y,step;
};
int check(node p)
{
    if(p.x>=0 && p.x<m && p.y>=0 && p.y<n && !vis[p.x][p.y]) //没有出界并且没有访问过
        return 1;
    else return 0;
}
int stair(node q,int i)
{
    if((a[q.x][q.y]=='-' && i%2==1 && (q.step-1)%2==0) ||  //楼梯开始时横着，人左右走，此时楼梯仍横着
       (a[q.x][q.y]=='-' && i%2==0 && (q.step-1)%2==1) ||  //楼梯开始时横着，人上下走，此时楼梯旋转成竖着
       (a[q.x][q.y]=='|' && i%2==0 && (q.step-1)%2==0) ||  //楼梯开始时竖着，人上下走，此时楼梯仍竖着
       (a[q.x][q.y]=='|' && i%2==1 && (q.step-1)%2==1) )   //楼梯开始时竖着，人左右走，此时楼梯旋转成横着
        return 1;
    else return 0;
}
void bfs()
{
    queue <node> Q;
    node p,q;
    p.x = sx;
    p.y = sy;
    p.step = 0;
    Q.push(p);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
 
        for(int i=0; i<4; i++)
        {
            q.x = p.x + dir[i][0];
            q.y = p.y + dir[i][1];
            q.step = p.step + 1;
 
            if(check(q) && a[q.x][q.y]!='*')
            {
                if(a[q.x][q.y]=='T')
                {
                    ans = q.step;
                    return;
                }
                if(a[q.x][q.y]=='.')
                {
                    vis[q.x][q.y] = true;
                    Q.push(q);
                }
                if(a[q.x][q.y]=='-' || a[q.x][q.y]=='|')
                {
                    if(stair(q,i))
                    {
                        q.x = q.x + dir[i][0];
                        q.y = q.y + dir[i][1];
                        if(check(q) && a[q.x][q.y]!='*')
                        {
                            if(a[q.x][q.y]=='T')
                            {
                                ans = q.step;
                                return;
                            }
                            vis[q.x][q.y] = true;
                            Q.push(q);
                        }
                    }
                    else
                    {
                        q = p;
                        q.step++;
                        Q.push(q);
                    }
                }
            }
        }
    }
}
int main()
{
    while(cin>>m>>n)
    {
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
            {
                cin>>ch;
                a[i][j] = ch;
                if(ch == 'S')
                {
                    sx = i;
                    sy = j;
                }
            }
        memset(vis,0,sizeof(vis));
        vis[sx][sy] = true;
        bfs();
        cout<<ans<<endl;
    }
    return 0;
}

L：Eight (hdu-1043)

题意:
八数码问题也称为九宫问题。在3×3的棋盘上摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。给出一个初始状态和一个目标状态，求出从初始状态转变成目标状态的移动棋子步数的最少值。

思路&代码:
八数码问题,不要求掌握但不妨碍你去掌握

直接看大佬的博客吧:
🔗外部链接1🔗
🔗外部链接2🔗

M：连连看 (hdu-1175)

题意:
…

思路:
bfs,可改进的bfs
改进思路:

一个一般的结论:

如果某一点记录的转向次数大于当前路径在该点的转向次数，那么还能从该点再发出一条路径来查找。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<queue>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
 
int n,m;
int map[1001][1001];
int v[1001][1001];
int x1,y1,x2,y2;
bool flag;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
struct node
{
	int x;
	int y;
	int trun;
}start,endd;
 queue<node> q;
 
bool judge(int x0,int y0)
{
	if(x0<0||x0>=n||y0<0||y0>=m)
		return true;
	if(x0==x2-1&&y0==y2-1)
		return false;
	if(map[x0][y0]!=0)
		return true;
	return false;
}
 
void bfs(int x0,int y0)
{
	int i;
 
	while(!q.empty())//队列清零
        q.pop();
 
	start.x=x0;
	start.y=y0;
	start.trun=-1;
	v[x0][y0]=1;
 
 
	q.push(start);//元素入列
 
	while(!q.empty())
	{
		start=q.front();
		q.pop();//元素出列
		if(start.trun>=2)	continue;
		for(i=0;i<4;i++)
		{
			endd.x=start.x+dir[i][0];
			endd.y=start.y+dir[i][1];
			endd.trun=start.trun+1;
 
			if(judge(endd.x,endd.y))	continue;//越界判断
 
			while(judge(endd.x,endd.y)==0)
			{
				if(endd.x==x2-1&&endd.y==y2-1)
				{
					flag=true;
					return;
				}
				if(v[endd.x][endd.y]==0)
				{
					q.push(endd);//元素入列
					v[endd.x][endd.y]=1;
				}
				endd.x+=dir[i][0];
				endd.y+=dir[i][1];
			}
		}
	}
}
 
int main()
{
	int t;
	int i,j;
 
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)	break;
 
		for(i=0;i<n;i++)
            for(j=0;j<m;j++)
			    scanf("%d",&map[i][j]);
 
        scanf("%d",&t);
 
		for(i=0;i<t;i++)
        {
            flag=false;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2&&y1==y2)//起点终点相同，不行
            {
                printf("NO\n");
                continue;
            }
            if(map[x1-1][y1-1]!=map[x2-1][y2-1]||map[x1-1][y1-1]==0||map[x2-1][y2-1]==0)//起点或者终点为0，起点终点不同，不行
            {
                printf("NO\n");
                continue;
            }
			memset(v,0,sizeof(v));
			bfs(x1-1,y1-1);
			if(flag)
				printf("YES\n");
            else
				printf("NO\n");
		}
	}
	return 0;
}

N：Dating with girls(2) (hdu-2579)

题意:
给你一个数T，表示有T组测试示例，接下来时r，c，k，表示迷宫的大小为r行c列，这个迷宫是非常奇怪的，
迷宫里有很多石头。这些石头会在t时刻消失，t的定义是k的倍数，在其他时候石头是依然存在的…是你
可以直接走的到地方，#表示石头，Y表示你的初始位子，G表示妹纸，保证只有一个Y和一个G，
每一秒你可以向左走，向右走，向上走，或者向下走。

思路:
J题的简单版?只需要在t倍数时刻判断一下是否可以走到石头点就行了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
    int x,y,output;
}now,nex;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
char a[105][105];
int vis[105][105][12];
int n,m,k;
void bfs(int x,int y)
{
    memset(vis,0,sizeof(vis));
    now.x=x;
    now.y=y;
    now.output=0;
    vis[x][y][0]=1;
    queue<node>s;
    s.push(now);
    while(!s.empty())
    {
        now=s.front();
        if(a[now.x][now.y]=='G')
        {
            printf("%d\n",now.output);
            return ;
        }
        s.pop();
        for(int i=0;i<4;i++)
        {
            nex.x=now.x+fx[i];
            nex.y=now.y+fy[i];
            nex.output=now.output+1;
            if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&vis[nex.x][nex.y][nex.output%k]==0)
            {
                if(a[nex.x][nex.y]=='.'||a[nex.x][nex.y]=='G'||a[nex.x][nex.y]=='Y')
                {
                    vis[nex.x][nex.y][nex.output%k]=1;
                    s.push(nex);
                }
                if(a[nex.x][nex.y]=='#'&&nex.output%k==0)
                {
                    vis[nex.x][nex.y][nex.output%k]=1;
                    s.push(nex);
                }
            }
        }
    }
    printf("Please give me another chance!\n");
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int sx,sy;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)
        {
            scanf("%s",a[i]);
            for(int j=0;j<m;j++)
            {
                if(a[i][j]=='Y')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        bfs(sx,sy);
    }
    return 0;
}

结语

下一节应该是二分查找&贪心?做好预习吧…