HNUCM-2020ACM集训队暑假练习题——搜索专题（基础）题解

矫情吗；* 2023-03-05 03:29 14阅读 0赞

# [A：hdu 1312-Red and Black][A_hdu 1312-Red and Black] #

## 题解 ##

板子题，上次课也有讲，bfs、dfs均可以（区别：bfs较快，dfs较简单）

## BFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    char mp[25][25];
    int vis[25][25],dir[4][2]={
        -1,0,1,0,0,-1,0,1};
    struct node{
        
        int x,y;
        node(int xx,int yy){
        
            x=xx,y=yy;
        }
    };
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0&&mp[x][y]=='.') return 1;
        return 0;
    }
    void bfs(int x,int y){
        
        int ans=1;
        queue<node>q;
        q.push(node(x,y));
        vis[x][y]=1;
        while(!q.empty()){
        
            node now=q.front();
            q.pop();
            for(int i=0;i<4;i++){
        
                int fx=now.x+dir[i][0];
                int fy=now.y+dir[i][1];
                if(check(fx,fy)){
        
                    vis[fx][fy]=1;
                    q.push(node(fx,fy));
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
        return ;
    }
    int main(){
        
        while(~scanf("%d%d",&m,&n)){
        
            if(!n&&!m) break;
            memset(vis,0,sizeof(vis));
            int sx,sy;
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='@'){
        
                        sx=i,sy=j;
                    }
                }
            }
            bfs(sx,sy);
        }
        return 0;
    }

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    char mp[25][25];
    int vis[25][25],dir[4][2]={
        -1,0,1,0,0,-1,0,1};
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0&&mp[x][y]=='.') return 1;
        return 0;
    }
    int ans;
    void dfs(int x,int y){
        
        for(int i=0;i<4;i++){
        
            int fx=x+dir[i][0];
            int fy=y+dir[i][1];
            if(check(fx,fy)){
        
                vis[fx][fy]=1;
                ans++;
                dfs(fx,fy);
            }
        }
    }
    int main(){
        
        while(~scanf("%d%d",&m,&n)){
        
            if(!n&&!m) break;
            memset(vis,0,sizeof(vis));
            int sx,sy;
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='@'){
        
                        sx=i,sy=j;
                    }
                }
            }
            ans=1,vis[sx][sy]=1;
            dfs(sx,sy);
            printf("%d\n",ans);
        }
        return 0;
    }

# [B：**POJ 3984-迷宫问题**][B_POJ 3984-] #

## 题解 ##

bfs板子题，可能稍微要处理的就是保存路径。简单看了下大家的代码，很多都是保存前驱结点，然后递归打印的。这里介绍一种更加简单的方法，直接可以保存在一个字符串中，具体见代码。

## BFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    int mp[10][10];
    int vis[10][10],dir[4][2]={
        -1,0,1,0,0,-1,0,1};
    struct node{
        
        int x,y;
        string s;
        node(int xx,int yy,string ss){
        
            x=xx,y=yy,s=ss;
        }
    };
    int check(int x,int y){
        
        if(x>=0&&x<5&&y>=0&&y<5&&vis[x][y]==0&&mp[x][y]==0) return 1;
        return 0;
    }
    void bfs(int sx,int sy){
        
        vis[sx][sy]=1;
        queue<node>q;
        q.push(node(sx,sy,"00"));
        while(!q.empty()){
        
            node now=q.front();
            q.pop();
            if(now.x==4&&now.y==4){
        
                for(int i=0;i<now.s.size();i+=2){
        
                    cout<<'('<<now.s[i]<<", "<<now.s[i+1]<<')'<<'\n';
                }
                break;
            }
            for(int i=0;i<4;i++){
        
                int fx=now.x+dir[i][0];
                int fy=now.y+dir[i][1];
                if(check(fx,fy)){
        
                    vis[fx][fy]=1;
                    string str=now.s;
                    str+=fx+'0';str+=fy+'0';
                    q.push(node(fx,fy,str));
                }
            }
        }
        return ;
    }
    int main(){
        
        for(int i=0;i<5;i++){
        
            for(int j=0;j<5;j++){
        
                scanf("%d",&mp[i][j]);
            }
        }
        bfs(0,0);
    }

# [C：hdu 1241-Oil Deposits][C_hdu 1241-Oil Deposits] #

## 题解 ##

八连通块板子题。dfs处理会稍微简单点。

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    char mp[110][110];
    int dirx[]={
        1,1,1,-1,-1,-1,0,0};
    int diry[]={
        1,-1,0,-1,0,1,-1,1};
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]=='@') return 1;
        return 0;
    }
    void dfs(int x,int y){
        
        for(int i=0;i<8;i++){
        
            int fx=x+dirx[i];
            int fy=y+diry[i];
            if(check(fx,fy)){
        
                mp[fx][fy]='*';
                dfs(fx,fy);
            }
        }
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            if(!n&&!m) break;
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
            }
            int ans=0;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='@'){
        
                        ans++;
                        mp[i][j]='*';
                        dfs(i,j);
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

# [D：POJ 2386-Lake Counting][D_POJ 2386-Lake Counting] #

## 题解 ##

同样是八连通块板子题。

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    char mp[110][110];
    int dirx[]={
        1,1,1,-1,-1,-1,0,0};
    int diry[]={
        1,-1,0,-1,0,1,-1,1};
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]=='W') return 1;
        return 0;
    }
    void dfs(int x,int y){
        
        for(int i=0;i<8;i++){
        
            int fx=x+dirx[i];
            int fy=y+diry[i];
            if(check(fx,fy)){
        
                mp[fx][fy]='.';
                dfs(fx,fy);
            }
        }
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
            }
            int ans=0;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='W'){
        
                        ans++;
                        mp[i][j]='.';
                        dfs(i,j);
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

# [E：hdu 2553-N皇后问题][E_hdu 2553-N] #

## 题解 ##

经典N皇后问题，由于n比较小，可以考虑回溯加剪枝即可。

但是暴力的回溯加剪枝会超时，可以考虑先打表，将n=1到10的结果保存到数组中，最后O(1)查询即可。

但是可以思考下，如果n比较大的话该用什么方法求解呢？可以看看网上大牛的博客学习学习。

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int l[20],r[20],col[20];
    int f[15],num;
    void dfs(int i,int n){
        
        if(i==n+1){
        
            num++;
            return ;
        }
        for(int j=1;j<=n;j++){
        
            if(l[i+j]==0&&r[i-j+n]==0&&col[j]==0){
        
                col[j]=1,l[i+j]=1,r[i-j+n]=1;
                dfs(i+1,n);
                col[j]=0,l[i+j]=0,r[i-j+n]=0;
            }
        }
        return ;
    }
    int main(){
        
        memset(f,0,sizeof(f));
        for(int i=1;i<=10;i++){
        
            num=0;
            memset(col,0,sizeof(col));
            memset(r,0,sizeof(r));
            memset(l,0,sizeof(l));
            dfs(1,i);
            f[i]=num;
        }
        int n;
        while(~scanf("%d",&n)&&n){
        
            printf("%d\n",f[n]);
        }
        return 0;
    }

# [F：变形课][F] #

## 题解 ##

简单DFS问题，直接暴力搜即可。

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    string s[maxn];
    int vis[maxn];
    int n,flag;
    void dfs(string s1) {
        
        if(flag) return ;
        if(s1[s1.size()-1]=='m') {
        
            flag=1;
            return ;
        }
        for(int i=1; i<=n; i++) {
        
            if(vis[i]==0&&s[i][0]==s1[s1.size()-1]) {
        
                vis[i]=1;
                dfs(s[i]);
                vis[i]=0;
            }
        }
    }
    int main() {
        
        while(cin>>s[1]) {
        
            n=1;
            while(cin>>s[++n]) {
        
                if(s[n]=="0") {
        
                    n--;
                    break;
                }
            }
            for(int i=1; i<=n; i++) {
        
                if(s[i][0]=='b') {
        
                    flag=0;
                    vis[i]=1;
                    dfs(s[i]);
                    vis[i]=0;
                    if(flag) break;
                }
            }
            if(flag) printf("Yes.\n");
            else printf("No.\n");
        }
    }

# [G：The Settlers of Catan][G_The Settlers of Catan] #

## 题解 ##

无向图最长路径，由于结点比较少，可以直接考虑对每个结点做dfs，在所有的路径中选择最长的即可。

## DFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5+5;
    int n,m,ans;
    int mp[110][110],vis[110][110];
    void dfs(int u,int cnt){
        
        ans=max(ans,cnt);
        for(int i=0;i<n;i++){
        
            if(mp[u][i]&&vis[u][i]==0){
        
                vis[u][i]=vis[i][u]=1;
                dfs(i,cnt+1);
                vis[u][i]=vis[i][u]=0;
            }
        }
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            if(n==0&&m==0) break;
            memset(mp,0,sizeof(mp));
            int u,v;
            for(int i=1;i<=m;i++){
        
                scanf("%d%d",&u,&v);
                mp[u][v]=mp[v][u]=1;
            }
            ans=0;
            for(int i=0;i<n;i++){
        
                memset(vis,0,sizeof(vis));
                dfs(i,0);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

# [H：棋盘问题][H] #

## 题解 ##

类似于n皇后，可以直接按照一行一行的放棋子，如果当前行能放，则直接跳转至下一行，且对放置过了的棋子计数加一；如果不能放，则直接跳转至下一行，放置过的棋子数量不变。

## DFS代码（cpp） ##

# [I：Catch That Cow][I_Catch That Cow] #

## 题解 ##

从题干中发现求最少的步数，当然优先考虑BFS，于是直接按照题意搜索即可。

## BFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5;
    int n,k;
    int vis[maxn+5];
    struct node{
        
        int x,step;
        node(int xx,int d){
        
            x=xx,step=d;
        }
    };
    void bfs(int x){
        
        int ans=0;
        queue<node>q;
        q.push(node(x,0));
        vis[x]=1;
        while(!q.empty()){
        
            node now=q.front();q.pop();
            if(now.x==k){
        
                ans=now.step;break;
            }
            if(now.x-1>=0&&vis[now.x-1]==0){
        
                vis[now.x-1]=1;q.push(node(now.x-1,now.step+1));
            }
            if(now.x+1<=maxn&&vis[now.x+1]==0){
        
                vis[now.x+1]=1;q.push(node(now.x+1,now.step+1));
            }
            if(2*now.x<=maxn&&vis[now.x+now.x]==0){
        
                vis[now.x+now.x]=1;q.push(node(2*now.x,now.step+1));
            }
        }
        printf("%d\n",ans);
    }
    int main(){
        
        while(~scanf("%d%d",&n,&k)){
        
            memset(vis,0,sizeof(vis));
            bfs(n);
        }
        return 0;
    }

# [J：Knight Moves][J_Knight Moves] #

## 题解 ##

同样是比较简单的搜索问题，由于求最短步数，同样优先考虑bfs，于是直接对起点做bfs即可。需要注意方向数组。

## BFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5;
    int vis[10][10],sx,sy,ex,ey;
    string s1,s2;
    int dirx[]={
        2,2,-2,-2,1,1,-1,-1};
    int diry[]={
        1,-1,1,-1,2,-2,2,-2};
    struct node{
        
        int x,y,step;
        node(int xx,int yy,int d){
        
            x=xx,y=yy,step=d;
        }
    };
    void bfs(int sx,int sy){
        
        int ans=0;
        queue<node>q;
        q.push(node(sx,sy,0));
        vis[sx][sy]=1;
        while(!q.empty()){
        
            node now=q.front();q.pop();
            if(now.x==ex&&now.y==ey){
        
                ans=now.step;break;
            }
            for(int i=0;i<8;i++){
        
                int fx=now.x+dirx[i];
                int fy=now.y+diry[i];
                if(vis[fx][fy]==0&&fx>=1&&fx<=8&&fy>=1&&fy<=8){
        
                    vis[fx][fy]=1;
                    q.push(node(fx,fy,now.step+1));
                    //cout<<fx<<' '<<fy<<' '<<now.step+1<<endl;
                }
            }
        }
        cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<ans<<" knight moves.\n";
        return ;
    }
    int main(){
        
        while(cin>>s1>>s2){
        
            sx=s1[0]-'a'+1,sy=s1[1]-'0';
            ex=s2[0]-'a'+1,ey=s2[1]-'0';
            //cout<<sx<<' '<<sy<<' '<<ex<<' '<<ey<<endl;
            memset(vis,0,sizeof(vis));
            bfs(sx,sy);
        }
        return 0;
    }

# [K：Find a way][K_Find a way] #

## 题解 ##

由于是需要求两个起点的最短路问题，可以直接对两个起点分别跑一次bfs，然后遍历整张地图，对每个’@'进行判断，选择最最短步数。

## BFS代码（cpp） ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #define inf 0x3f3f3f3f
    #define ll long long
    #define pi acos(-1.0);
    using namespace std;
    const int maxn=1e5;
    char mp[210][210];
    int vis[210][210],dis1[210][210],dis2[210][210];
    int dir[4][2]={
        -1,0,1,0,0,-1,0,1};
    int n,m;
    struct node{
        
        int x,y,step;
        node(int xx,int yy,int d){
        
            x=xx,y=yy,step=d;
        }
    };
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&mp[x][y]!='#') return 1;
        return 0;
    }
    void bfs(int x,int y,int flag){
        
        queue<node>q;
        q.push(node(x,y,0));
        vis[x][y]=1;
        while(!q.empty()){
        
            node now=q.front();q.pop();
            if(mp[now.x][now.y]=='@'){
        
                if(flag==0) dis1[now.x][now.y]=now.step;
                else dis2[now.x][now.y]=now.step;
            }
            for(int i=0;i<4;i++){
        
                int fx=now.x+dir[i][0];
                int fy=now.y+dir[i][1];
                if(check(fx,fy)){
        
                    vis[fx][fy]=1;
                    q.push(node(fx,fy,now.step+1));
                }
            }
        }
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            int sx1,sy1,sx2,sy2;
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='Y'){
        
                        sx1=i,sy1=j;
                    }
                    if(mp[i][j]=='M'){
        
                        sx2=i,sy2=j;
                    }
                }
            }
            memset(dis1,0,sizeof(dis1));
            memset(dis2,0,sizeof(dis2));
            memset(vis,0,sizeof(vis));
            bfs(sx1,sy1,0);
            memset(vis,0,sizeof(vis));
            bfs(sx2,sy2,1);
            int ans=inf;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='@'&&dis1[i][j]&&dis2[i][j]&&dis1[i][j]+dis2[i][j]<ans){
        
                        ans=dis1[i][j]+dis2[i][j];
                    }
                }
            }
            printf("%d\n",ans*11);
        }
        return 0;
    }

# [L：Find The Multiple][L_Find The Multiple] #

## 题解 ##

数据比较弱，用long long保存或者 \_int64都可以过，知道这个之后，题目就变得很水了，直接dfs暴力搜即可。

## DFS代码（cpp） ##

# [M：Dungeon Master][M_Dungeon Master] #

## 题解 ##

经典三维迷宫问题求最短路问题，只需考虑方向数组由2维变3维即可，直接对起点跑一遍bfs即可。

## BFS代码（cpp） ##

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=1e6;
    const double eps=1e-8;
    char mp[35][35][35];
    int vis[35][35][35];
    int row,col,height;
    int sx,sy,sz,ex,ey,ez;
    int dirx[6]={
        0,0,0,0,1,-1};
    int diry[6]={
        0,0,-1,1,0,0};
    int dirz[6]={
        1,-1,0,0,0,0};
    int flag;         //判断有没有解
    struct node{
        
        int x,y,z;
        int dis;
        node(int xx,int yy,int zz,int diss){
        
            x=xx;
            y=yy;
            z=zz;
            dis=diss;
        }
    };
    int check(int x,int y,int z){
        
        if(x<0||y<0||z<0||x>=height||y>=row||z>=col){
        
            return 0;
        }
        if(vis[x][y][z]||mp[x][y][z]=='#'){
        
            return 0;
        }
        return 1;
    }
    void bfs(){
        
        queue<node>q;
        q.push(node(sx,sy,sz,0));
        while(!q.empty()){
        
            node now=q.front();
            if(now.x==ex&&now.y==ey&&now.z==ez){
        
                printf("Escaped in %d minute(s).\n",now.dis);
                flag=1;
                return ;
            }
            q.pop();
            for(int i=0;i<6;i++){
        
                int fx=now.x+dirx[i];
                int fy=now.y+diry[i];
                int fz=now.z+dirz[i];
                if(check(fx,fy,fz)){
        
                    vis[fx][fy][fz]=1;
                    q.push(node(fx,fy,fz,now.dis+1));
                }
            }
        }
        return ;
    }
    int main(){
        
        while(~scanf("%d%d%d",&height,&row,&col)){
        
            if(height==0&&row==0&&col==0){
        
                break;
            }
            memset(vis,0,sizeof(vis));
            memset(mp,0,sizeof(mp));
            for(int i=0;i<height;i++){
        
                for(int j=0;j<row;j++){
        
                    scanf("%s",mp[i][j]);
                }
                getchar();
            }
            flag=0;
            int flag1=0,flag2=0;
            for(int i=0;i<height;i++){
        
                for(int j=0;j<row;j++){
        
                    for(int k=0;k<col;k++){
        
                        if(mp[i][j][k]=='S'){
        
                            sx=i;
                            sy=j;
                            sz=k;
                            flag1=1;
                        }
                        if(mp[i][j][k]=='E'){
        
                            ex=i;
                            ey=j;
                            ez=k;
                            flag2=1;
                        }
                        if(flag1&&flag2){
        
                            break;
                        }
                    }
                    if(flag1&&flag2)
                        break;
                }
                if(flag1&&flag2){
        
                    break;
                }
            }
            bfs();
            if(flag==0){
        
                printf("Trapped!\n");
            }
        }
        return 0;
    }

# [N：Rescue][N_Rescue] #

## 题解 ##

BFS+优先队列

需要注意：有多个’r’（即：有多个起点）

常规解法：对每个起点跑一次bfs，然后从中找出最少步数

优秀解法：直接对终点跑一次bfs，由于是优先队列，所以遇到’r’，即可结束。

下面是欧阳亨杰的代码：

## BFS代码（cpp） ##

#include <bits/stdc++.h>
    
    using namespace std;
    int n,m,vis[205][205],dx,dy,flag;
    char mp[205][205];
    int d[4][2]={
        1,0,-1,0,0,1,0,-1};
    struct node
    {
        
        int x,y,step;
        bool operator < (const node &a)const
        {
        
            return a.step<step;
        }
    };
    void bfs()
    {
        
        memset(vis,0,sizeof(vis));
        node a;
        a.x=dx;
        a.y=dy;
        a.step=0;
        priority_queue<struct node>p;
        p.push(a);
        while(!p.empty())
        {
        
            a=p.top();
            p.pop();
            if(mp[a.x][a.y]=='r')
            {
        
                flag=1;
                printf("%d\n",a.step);
                return ;
            }
            for(int i=0;i<4;i++)
            {
        
                node next;
                next.x=a.x+d[i][0];
                next.y=a.y+d[i][1];
                next.step=a.step;
                if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]!='#'&&!vis[next.x][next.y])
                {
        
                    vis[next.x][next.y]=1;
                    if(mp[next.x][next.y]=='x')
                        next.step+=2;
                    else
                        next.step+=1;
                    p.push(next);
                }
            }
        }
    }
    int main()
    {
        
        while(~scanf("%d %d",&n,&m))
        {
        
            flag=0;
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                {
        
                    cin>>mp[i][j];
                    if(mp[i][j]=='a')
                    {
        
                        dx=i;
                        dy=j;
                    }
                }
            bfs();
            if(!flag)
                printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
        return 0;
    }

# [O：哈密顿绕行世界问题][O] #

## 题解 ##

直接dfs暴搜即可，看似比较复杂，实则很简单。

## DFS代码（cpp） ##

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int mp[30][30];         //邻接矩阵
    int path[30];          //存放前驱结点
    int vis[30];           //标记数组
    
    int m,t;           //m表示出发结点，t表示路径的条数
    
    void DFS(int k,int sum)
    {
        
        int i;
        if(sum==20&&mp[m][k]==1)
        {
        
            printf("%d: ",t);
            for(int i=1;i<=20;i++)
                printf(" %d",path[i]);
            printf(" %d\n",m);
            t++;
            return ;
        }
        for(int i=1;i<=20;i++)
        {
        
            if(vis[i]==0&&mp[k][i]==1)
            {
        
                vis[i]=1;
                path[sum+1]=i;
                DFS(i,sum+1);
                vis[i]=0;
            }
        }
        return ;
    }
    int main()
    {
        
        int i;
        memset(mp,0,sizeof(mp));
        int a,b,c;
        for(int i=1;i<=20;i++)
        {
        
            scanf("%d%d%d",&a,&b,&c);
            mp[i][a]=mp[i][b]=mp[i][c]=1;
        }
        while(~scanf("%d",&m))
        {
        
            if(m==0)
                break;
            vis[m]=1;
            path[1]=m;
            t=1;
            DFS(m,1);
        }
        return 0;
    }

# [P：Prime Path][P_Prime Path] #

## 题解 ##

题意不难，给定a，b；需要按照题目规定的每次改变一位，且保证改变后的数字是素数，问最少需要多少步能从a变成b。

常规解法：直接对个位、十位、百位、千位进行搜索。

简化代码方式：直接用字符串存数字，然后对字符串进行简单处理。下面给出常规解法。

## BFS代码（cpp） ##

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=1e5;
    const double eps=1e-8;
    int t;
    int n,m;
    int flag;
    bool vis[10010];
    int check[maxn+10];
    void init(){
        
        memset(vis,true,sizeof(vis));
        vis[1]=false;
        for(int i=2;i<=maxn;i++){
        
            for(int j=i*2;j<=maxn;j+=i){
        
                vis[j]=false;
            }
        }
        return ;
    }
    struct node{
        
        int x;
        int step;
        node(int xx,int s){
        
            x=xx;
            step=s;
        }
    };
    void bfs(int num,int step){
        
        check[num]=1;
        queue<node>q;
        q.push(node(num,step));
        while(!q.empty()){
        
            node now=q.front();
            q.pop();
            if(now.x==m){
        
                printf("%d\n",now.step);
                flag=1;
                return ;
            }
            for(int i=0;i<=9;i++){
                 //个位
                int fx=(now.x/10)*10+i;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=0;i<=9;i++){
                 //十位
                int fx=(now.x/100)*100+i*10+now.x%10;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=0;i<=9;i++){
                 //百位
                int fx=(now.x/1000)*1000+i*100+now.x%100;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
            for(int i=1;i<=9;i++){
                 //千位
                int fx=i*1000+now.x%1000;
                if(check[fx]==0&&vis[fx]==true){
        
                    q.push(node(fx,now.step+1));
                    check[fx]=1;
                }
            }
        }
        return ;
    }
    int main(){
        
        init();
        scanf("%d",&t);
        while(t--){
        
            flag=0;
            memset(check,0,sizeof(check));
            scanf("%d%d",&n,&m);
            bfs(n,0);
            if(flag==0){
        
                printf("Impossible\n");
            }
        }
        return 0;
    }

# [Q：Tempter of the Bone][Q_Tempter of the Bone] #

## 题解 ##

DFS+奇偶剪枝

[奇偶剪枝博客][Link 1]

了解了奇偶剪枝后，这题就很水了，下面是廖世兴的代码。

## DFS代码（cpp） ##

#include <iostream>
    #include <string.h>
    #include <stdlib.h>
    using namespace std;
    char graph[10][10];
    int sx,sy,dx,dy,n,m,k;
    bool flag;
    bool visit[10][10];
    int turn[4][2]={
        1,0,-1,0,0,1,0,-1};
    void dfs(int x,int y,int count)
    {
        
    	if(flag)return;
    	if(x==dx&&y==dy&&count==k){
        
    		flag=1;return;
    	}
    	if(count>=k)return;
    	if(graph[x][y]!='X'){
        
    		for(int i=0;i<4;i++){
        
    			int mx = x+turn[i][0];
    			int my = y+turn[i][1];
    			if(graph[mx][my]!='X'&&mx>=1&&mx<=n&&my>=1&&my<=m&&!visit[mx][my]){
        
    				visit[mx][my] = 1;
    				dfs(mx,my,count+1);
    				visit[mx][my] = 0;
    			}
    		}
    	}
    }
    int main()
    {
        
    	while(cin>>n>>m>>k&&n&&m&&k){
        
    		for(int i=1;i<=n;i++){
        
    			for(int j=1;j<=m;j++){
        
    				cin>>graph[i][j];
    				if(graph[i][j]=='S')sx = i,sy = j;
    				if(graph[i][j]=='D')dx = i,dy = j;
    			}
    		}
    		if(abs(sx-dx)+abs(sy-dy)>k||(sx+sy+dx+dy+k)%2==1){
          //奇偶剪枝
    			cout<<"NO"<<endl;
    			continue;
    		}
    		memset(visit,0,sizeof(visit));
    		flag=0,visit[sx][sy] = 1;
    		dfs(sx,sy,0);
    		if(flag)cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
    }

# [R：Transportation][R_Transportation] #

## 题解 ##

搜索+思维。具体见代码。

## DFS代码（cpp） ##

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    /**其中s表示出发站点，e表示末站点，p表示乘客数量*/
    struct Order
    {
        
        int s,e,p;
    }order[30];
    int down[10];          //存放在某一站下车的乘客数量
    int capacity,stopNum,t;     //分别表示车的最大乘客量，站点个数，order数量
    int maxValue;            //表示最终可以获得的最大利益
    
    int cmp(Order x,Order y)
    {
        
        if(x.s!=y.s)
            return x.s<y.s;
        else
            return x.e<y.e;
    }
    
    void dfs(int i,int passengerNum,int value)     //分别表示已经测试数据的个数，此次乘客数，当前已经获得的利益
    {
        
        /**递归结束条件*/
        if(i==t)
        {
        
            maxValue=max(maxValue,value);
            return ;
        }
        /**把站点为0排除了*/
        if(i>0)
        {
        
            for(int j=order[i-1].s+1;j<=order[i].s;j++)
                passengerNum-=down[j];
        }
        if(passengerNum+order[i].p<=capacity)
        {
        
            down[order[i].e]+=order[i].p;
            dfs(i+1,passengerNum+order[i].p,value+order[i].p*(order[i].e-order[i].s));
            down[order[i].e]-=order[i].p;
        }
        dfs(i+1,passengerNum,value);
    }
    
    int main()
    {
        
        while(~scanf("%d%d%d",&capacity,&stopNum,&t))
        {
        
            if(capacity==0&&stopNum==0&&t==0)
                break;
            for(int i=0;i<t;i++)
                scanf("%d%d%d",&order[i].s,&order[i].e,&order[i].p);
            /**排序*/
            sort(order,order+t,cmp);
    
            maxValue=0;
            dfs(0,0,0);
    
            printf("%d\n",maxValue);
        }
        return 0;
    }

# [S：Fliptile][S_Fliptile] #

# [T：Shuffle’m Up][T_Shuffle_m Up] #

# [U：Pots][U_Pots] #

## 题解 ##

思路很简单，直接BFS即可，可能存储路径时会有点麻烦，但是能很好的训练编码能力。

小技巧：一般存储路径建议用字符串存，这样比存前驱要更加方便。

## BFS代码（cpp） ##

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1e5+10;
    int a,b,c;
    int vis[110][110];
    struct node{
        
        int v1,v2,step;
        string str;
        node(int vv1,int vv2,string ss,int s){
        
            v1=vv1;
            v2=vv2;
            step=s;
            str=ss;
        }
    };
    int check(int x,int y){
        
        if(vis[x][y]==0&&x>=0&&x<=a&&y>=0&&y<=b)
            return 1;
        else{
        
            return 0;
        }
    }
    int flag=0;
    void bfs(){
        
        queue<node>q;
        q.push(node(0,0,"",0));
        while(!q.empty()){
        
            node now=q.front();
            q.pop();
            if(now.v1==c||now.v2==c){
        
                cout<<now.step<<endl;
                cout<<now.str;
                flag=1;
                return ;
            }
            int x,y;
    
            //FILL操作
            x=a;
            y=now.v2;
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"FILL(1)\n",now.step+1));
            }
            x=now.v1;
            y=b;
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"FILL(2)\n",now.step+1));
            }
    
            //DROP操作
            x=0;
            y=now.v2;
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"DROP(1)\n",now.step+1));
            }
            x=now.v1;
            y=0;
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"DROP(2)\n",now.step+1));
            }
    
            //POUR操作
            int num=b-now.v2;
            if(now.v1>=num){
        
                x=now.v1-num;
                y=b;
            }
            else{
        
                x=0;
                y=now.v2+now.v1;
            }
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"POUR(1,2)\n",now.step+1));
            }
            num=a-now.v1;
            if(now.v2>=num){
        
                x=a;
                y=now.v2-num;
            }
            else{
        
                x=now.v1+now.v2;
                y=0;
            }
            if(check(x,y)){
        
                vis[x][y]=1;
                q.push(node(x,y,now.str+"POUR(2,1)\n",now.step+1));
            }
        }
        return ;
    }
    int main(){
        
        while(~scanf("%d%d%d",&a,&b,&c)){
        
            flag=0;
            bfs();
            if(flag==0){
        
                printf("impossible\n");
            }
        }
        return 0;
    }

[A_hdu 1312-Red and Black]: http://acm.hdu.edu.cn/showproblem.php?pid=1312
[B_POJ 3984-]: http://poj.org/problem?id=3984
[C_hdu 1241-Oil Deposits]: http://acm.hdu.edu.cn/showproblem.php?pid=1241
[D_POJ 2386-Lake Counting]: http://poj.org/problem?id=2386
[E_hdu 2553-N]: http://acm.hdu.edu.cn/showproblem.php?pid=2553
[F]: http://acm.hdu.edu.cn/showproblem.php?pid=1181
[G_The Settlers of Catan]: http://poj.org/problem?id=2258
[H]: http://poj.org/problem?id=1321
[I_Catch That Cow]: http://poj.org/problem?id=3278
[J_Knight Moves]: http://acm.hdu.edu.cn/showproblem.php?pid=1372
[K_Find a way]: http://acm.hdu.edu.cn/showproblem.php?pid=2612
[L_Find The Multiple]: http://poj.org/problem?id=1426
[M_Dungeon Master]: http://poj.org/problem?id=2251
[N_Rescue]: http://acm.hdu.edu.cn/showproblem.php?pid=1242
[O]: http://acm.hdu.edu.cn/showproblem.php?pid=2181
[P_Prime Path]: http://poj.org/problem?id=3126
[Q_Tempter of the Bone]: http://acm.hdu.edu.cn/showproblem.php?pid=1010
[Link 1]: https://www.cnblogs.com/wkfvawl/p/9337156.html
[R_Transportation]: http://poj.org/problem?id=1040
[S_Fliptile]: http://poj.org/problem?id=3279
[T_Shuffle_m Up]: http://poj.org/problem?id=3087
[U_Pots]: http://poj.org/problem?id=3414