简单搜索专题

2016-08-10

题源：http://acm.hust.edu.cn/vjudge/contest/65959#overview

A - 棋盘问题

思路：要放k个棋子，dfs贪心深搜。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=10;
int mmap[MAXN][MAXN];  //棋盘
bool vis[MAXN];    //标记数组 vis[1]=true表示1行已放棋子
int n,k;

int ans;
int sum;  //记录已经放了多少个旗子

void dfs(int i)
{
    if(sum==k)
    {
        ans++;
        return;
    }
    if(i>=n) return;
    for(int j=0;j<n;j++)
    {
        if(!vis[j]&&mmap[i][j])
        {
            sum++;
            vis[j]=true;
            dfs(i+1);
            sum--;
            vis[j]=false;
        }
    }
    dfs(i+1);  //第i行不放
}

int main()
{
    while(cin>>n>>k&&n!=-1&&k!=-1)
    {
        char temp;
        ans=0;
        sum=0;
        memset(mmap,0,sizeof(mmap));
        memset(vis,false,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>temp;
                if(temp=='#')
                    mmap[i][j]=1;
            }
        }
        dfs(0);
        cout<<ans<<endl;

    }

    return 0;
}
View Code

B - Dungeon Master

题意：给你一个三维的矩阵，L层，R行，L列。起点为S，终点为E，'#'表示墙，'.'表示路。可以上下左右前后六个方向走，每走一格耗时1min，问怎样最快到达终点。

思路：用广搜的特性：最短路，bfs即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN=50;

char mmap[MAXN][MAXN][MAXN];   //地图
int L,R,C;              //L表示层数，R表示行数，C表示列数


bool vis[MAXN][MAXN][MAXN];   //标记数组
int path[MAXN][MAXN][MAXN];   //记录路径值
struct cubes     //三位坐标点结构体
{
    int l,r, c;
} s,e;     //s表示起点，e表示终点
queue<cubes> q;


bool bfs(cubes x)   //出入起点s给x
{
    memset(path,0,sizeof(path));
    memset(vis,false,sizeof(vis));
    vis[x.l][x.r][x.c]=true;
    bool escape=false;     //标记是否成功逃离迷宫
    while(!q.empty()) q.pop();
    int dl[6]= {0,0,0,0,1,-1};    //前后上下左右6个方向
    int dr[6]= {1,-1,0,0,0,0};
    int dc[6]= {0,0,-1,1,0,0};
    cubes now,tmp;
    tmp=x;
    q.push(tmp);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(mmap[now.l][now.r][now.c]=='E')
        {
            escape=true;
            break;
        }

        for(int i=0; i<6; i++)
        {
            tmp.l=now.l+dl[i];           //6个方向都找一遍
            tmp.r=now.r+dr[i];
            tmp.c=now.c+dc[i];

            if(tmp.l>0&&tmp.l<=L&&tmp.r>0&&tmp.r<=R&&tmp.c>0&&tmp.c<=C)   //判断越界
                if(!vis[tmp.l][tmp.r][tmp.c]&&(mmap[tmp.l][tmp.r][tmp.c]=='.'||mmap[tmp.l][tmp.r][tmp.c]=='E'))
                {
                    vis[tmp.l][tmp.r][tmp.c]=true;
                    path[tmp.l][tmp.r][tmp.c]=path[now.l][now.r][now.c]+1;
                    q.push(tmp);
                }
        }


    }
    return escape;
}

int main()
{

    while(cin>>L>>R>>C&&L&&R&&C)
    {
        for(int l=1; l<=L; l++)
        {
            for(int r=1; r<=R; r++)
            {
                for(int c=1; c<=C; c++)
                {
                    cin>>mmap[l][r][c];
                    if(mmap[l][r][c]=='S')
                    {
                        s.l=l;
                        s.c=c;
                        s.r=r;
                    }
                    if(mmap[l][r][c]=='E')
                    {
                        e.l=l;
                        e.r=r;
                        e.c=c;
                    }
                }
            }
        }

        if(bfs(s))
            cout<<"Escaped in "<<path[e.l][e.r][e.c]<<" minute(s)."<<endl;
        else
            cout<<"Trapped!"<<endl;
        /*for(int i=1; i<=L; i++)
        {
            for(int j=1; j<=R; j++)
            {
                for(int k=1; k<=C; k++)
                    cout<<path[i][j][k]<<" ";
                cout<<endl;
            }
            cout<<endl;

        }*/


    }

    return 0;
}
View Code

C - Catch That Cow

题意：一条直线上，你在点N处，要到达目标点K点。

走的时候只能有两种选择（假如现在在X点）：

1.到达x-1点或者到达x+1点；2.到达x*2点处。

每种选择耗时相同，问怎样最快到达目标点。

思路：bfs....直接贴代码

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN=100005;
int N,K;
int path[MAXN*2+1];  //记录步数
bool vis[MAXN*2+1];  //标记数组
queue<int> q;
void bfs(int N)
{
    memset(path,0,sizeof(path));
    memset(vis,false,sizeof(vis));

    while(!q.empty()) q.pop();
    int now;
    q.push(N);
    vis[N]=true;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now==K)
        {
            break;
            //return;
        }

        if(!vis[now+1]&&(now+1)<=100000&&(now+1)>=0)
        {

            vis[now+1]=true;
            path[now+1]=path[now]+1;
            q.push(now+1);
        }
        if(!vis[now-1]&&(now-1)<=100000&&(now-1)>=0)
        {
            vis[now-1]=true;
            path[now-1]=path[now]+1;
            q.push(now-1);
        }
        if(!vis[now*2]&&(now*2)<=100000&&(now*2)>=0)
        {
            vis[now*2]=true;
            path[now*2]=path[now]+1;
            q.push(now*2);
        }


    }
}

int main()
{
    while(cin>>N>>K)
    {
        if(N>K) cout<<N-K<<endl;  //要注意这个地方，起点>终点
        else
        {
            bfs(N);
            cout<<path[K]<<endl;
        }
    }
    return 0;
}
View Code

D - Fliptile

题意：给你一个矩阵，每个点有一个带数字的牌子（一面为0，一面为1），你可以翻动任意牌子，使所有牌子为0的面朝上，翻动规则如下：

翻动某一牌子，该牌子的上下左右方向的牌子会跟着它一起翻动。

问最少多少次可以完成任务。

思路：bfs+二进制压缩。这里有一个很"显然"（看了别人的报告才"显然"的）的规律：从第二行开始，每行翻牌的时候要看上一行的状态，如果上一行为1，那么就翻，使上一行为0，否则就不翻。直到翻到最后一行，判断最后一行是否全为0，如果是，则记录翻的次数。如果不是，则直接返回。

那么问题就好解决了，只需把第一行的状态枚举一遍即可，求出最小的次数。

因为只有0,1。所以可以用二进制记录。

看代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN=16;

int mmap[MAXN][MAXN];
int f[MAXN][MAXN];  //mmap记录现在状态，为0还是1。f记录翻转状态,0为不翻，1为翻
int t[MAXN][MAXN];  //临时数组

int m,n;    //m行n列
int ans,cnt;   //cnt代表步数
int p;        //记录最优解时 第一行怎样翻

int di[5]={0,-1,1,0,0};   //记录原地和四个方向
int dj[5]={0,0,0,-1,1};

void flip(int x,int y)
{

    cnt++,f[x][y]=1;
    for(int i=0;i<5;i++)
    {
        int ti=x+di[i];
        int tj=y+dj[i];
        if(ti>-1&&tj>-1)  //判断是否越界
            t[ti][tj]^=1;   //0变1,1变0
    }

}

bool ok(int k)   //k记录第0行的现状态
{
    cnt=0;          //初始化步数
    memcpy(t,mmap,sizeof(t)); //将原始数组拷贝到临时数组
    for(int j=0;j<n;j++)       //先判断第0行哪一列为1，然后翻转
    {
        if(k&(1<<(n-1-j)))
            flip(0,j);
    }

    for(int i=1;i<m;i++)     //第0行翻完了，从1行开始翻一直到m-1行
    {
        for(int j=0;j<n;j++)
        {
            if(t[i-1][j])    //如果该列上一行为1，就翻转
                flip(i,j);
        }
    }

    for(int j=0;j<n;j++)     //判断最后一行有没有1，如果有返回false
        if(t[m-1][j]) return false;
    return true;
}

int main()
{
    while(cin>>m>>n)
    {

        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
                cin>>mmap[i][j];
        }

        ans=m*n+1;   //更新记录最小步数
        p=-1;
        for(int k=0;k<(1<<n);k++)
        {

            if(ok(k)&&ans>cnt)
            {
                p=k;
                ans=cnt;
            }
        }

        memset(f,0,sizeof(f));
        if(p>=0)   //说明该题有解
        {
            ok(p);   //再模拟一下第0行,然后输出f
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                    printf("%d%c",f[i][j],j<n-1?' ':'
');
        }
        else
            puts("IMPOSSIBLE");


    }
    return 0;
}
View Code

 E - Find The Multiple

题意：给你一个正整数n,编程找到一个能整除n的最小数m,m只能由0,1组成。

思路：bfs，搜的时候从1开始，每次由两种选择，1*10,1*10+1，知道搜到第一个满足题意的数即可。（嫌慢的话，还有一个方法，打表。。毕竟数据不大）

代码：

 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 
 7 #define ll long long
 8 
 9 
10 using namespace std;
11 
12 
13 
14 ll n;
15  queue<ll> q;
16 void bfs(ll s)
17 {
18 
19 
20     while(!q.empty()) q.pop();
21     q.push(s);
22     while(!q.empty())
23     {
24         ll tmp=q.front();
25         q.pop();
26         if(tmp%n==0)
27         {
28             cout<<tmp<<endl;
29             break;
30         }
31         q.push(tmp*10);
32         q.push(tmp*10+1);
33     }
34 
35 }
36 
37 int main()
38 {
39     while(cin>>n&&n)
40     {
41 
42        if(n==1)
43         cout<<1<<endl;
44        else
45             bfs(1);
46     }
47 
48     return 0;
49 }
50 
51 /*
52 int main()
53 {
54     ll arr[]={1,10,111,100,10,1110,1001,1000,111111111,10,
55               11,11100,1001,10010,1110,10000,11101,1111111110,11001,
56               100,10101,110,110101,111000,100,10010,1101111111,100100,
57               1101101,1110,111011,100000,111111,111010,10010,11111111100,
58               111,110010,10101,1000,11111,101010,1101101,1100,1111111110,
59               1101010,10011,1110000,1100001,100,100011,100100,100011,11011111110,110,
60               1001000,11001,11011010,11011111,11100,100101,1110110,1111011111,1000000,10010,
61               1111110,1101011,1110100,10000101,10010,10011,111111111000,10001,1110,11100,1100100,
62               1001,101010,10010011,10000,1111111101,111110,101011,1010100,111010,11011010,11010111,
63               11000,11010101,1111111110,1001,11010100,10000011,100110,110010,11100000,11100001,11000010,
64               111111111111111111,100,101,1000110,11100001,1001000,101010,1000110,100010011,110111111100,1001010111,
65               110,111,10010000,1011011,110010,1101010,110110100,10101111111,110111110,100111011,111000,11011,1001010,
66               10001100111,11101100,1000,11110111110,11010011,10000000,100100001,10010,101001,11111100,11101111,11010110,
67               11011111110,11101000,10001,100001010,110110101,100100,10011,100110,1001,1111111110000,11011010,100010,1100001,
68               11100,110111,11100,1110001,11001000,10111110111,10010,1110110,1010100,10101101011,100100110,100011,100000,11101111,
69               11111111010,1010111,1111100,1111110,1010110,11111011,10101000,10111101,111010,1111011111,110110100,1011001101,
70               110101110,100100,110000,100101111,110101010,11010111,11111111100,1001111,10010,100101,110101000,1110,100000110,
71               1001011,1001100,1010111010111,110010,11101111,111000000,11001,111000010,101010,110000100,1101000101,
72               1111111111111111110,111000011,1000};
73     int n;
74     while(cin>>n&&n)
75         cout<<arr[n-1]<<endl;
76     return 0;
77 
78 }
79 */
View Code

F - Prime Path

题意：输入m,n。求出并打印m,n之间的素数路径有多少个元素。下一个素数由上一个素数变换一位数字而来。

思路：按照题意模拟一下，直接搜即可。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 const int MAXN=10001;
 10 
 11 int m,n;
 12 int step;
 13 int mmin=-1;
 14 int path[MAXN];  //存路径长度
 15 int vis[MAXN];  //标记数组
 16 
 17 bool is_prime(int a)   //素数判断
 18 {
 19     if(a<2) return false;
 20     for(int i=2;i*i<=a;i++)
 21     {
 22         if(a%i==0)
 23             return false;
 24     }
 25     return true;
 26 }
 27 
 28 void change(int &tmp,int i,int num)  //把tmp的第i位变成num，（从右往左数第i位）
 29 {
 30    int di=1;
 31    for(int ii=0;ii<i;ii++)
 32         di*=10;
 33     di/=10;
 34     int tmp1=tmp/di;
 35     int tmp2=tmp1%10;
 36     tmp2*=di;
 37     tmp-=tmp2;
 38     tmp+=num*di;
 39 
 40 }
 41 
 42 void bfs(int x)
 43 {
 44     queue<int> q;
 45     memset(path,0,sizeof(path));
 46     memset(vis,false,sizeof(vis));
 47 
 48     while(!q.empty()) q.pop();
 49     q.push(x);
 50     vis[x]=true;
 51     while(!q.empty())
 52     {
 53         int tmp=q.front();
 54         //cout<<tmp<<" ап:";
 55         q.pop();
 56         if(tmp==n)   //出口
 57         {
 58             mmin=tmp;
 59             break;
 60         }
 61 
 62         int mtmp=tmp;
 63         for(int i=1;i<=4;++i)
 64         {
 65             for(int num=0;num<10;++num)
 66             {
 67 
 68                   change(mtmp,i,num);
 69                   if(is_prime(mtmp)&&!vis[mtmp]&&mtmp>=1000)
 70                   {
 71                       path[mtmp]=path[tmp]+1;
 72 
 73                       vis[mtmp]=true;
 74                       q.push(mtmp);
 75                       //cout<<mtmp<<"---";
 76 
 77                   }
 78                   mtmp=tmp;
 79 
 80             }
 81         }
 82         //cout<<endl;
 83     }
 84 }
 85 
 86 int main()
 87 {
 88 
 89     int T;
 90     cin>>T;
 91     while(T--)
 92     {
 93 
 94         cin>>m>>n;
 95         if(m>n) swap(m,n);
 96         bfs(m);
 97         cout<<path[mmin]<<endl;
 98     }
 99 
100     return 0;
101 }
View Code

 G - Shuffle'm Up

题意：两摞牌s1,s2，洗牌的时候按下图洗。

洗完之后变成s12,然后把s12上面部分的牌变成s1,剩下的变成s2，继续重复图中步骤洗牌。

牌用大写字母代替，输入s1,s2，和sans（都是字符串），问能否用最小的步数洗牌变成sans。能就输出多少步，否则输出-1。

思路：模拟即可，用map记录一下每种结果是否已经出现过。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <map>
  6 using namespace std;
  7 
  8 const int MAXN=101;
  9 char s1[MAXN],s2[MAXN];
 10 char s12[MAXN<<1|1];
 11 char sans[MAXN<<1|1];   //目标字符串（洗完牌之后的结果）
 12 
 13 map<string,bool> mmap;
 14 
 15 void shuffle(char s1[],char s2[],char s12[])  //洗牌过程
 16 {
 17     memset(s12,'',sizeof(s12));
 18     int len1=strlen(s1);
 19     int len2=strlen(s2);
 20     int len12=len1+len2;
 21     int i=0,j=0,k=0;
 22 
 23     int signal=1;
 24     while(k<len12)
 25     {
 26         if(signal)
 27             s12[k++]=s2[j++];
 28         else
 29             s12[k++]=s1[i++];
 30         signal^=1;
 31     }
 32 }
 33 
 34 void split(char s12[],char s1[],char s2[])  //把s12拆分成s1,s2
 35 {
 36     memset(s1,'',sizeof(s1));
 37     memset(s2,'',sizeof(s2));
 38     int len12=strlen(s12);
 39     int len1,len2;
 40     len1=len2=len12/2;
 41     int k=0;
 42     for(int i=0;i<len1;i++)
 43         s1[i]=s12[k++];
 44     for(int j=0;j<len2;j++)
 45         s2[j]=s12[k++];
 46 }
 47 
 48 int main()
 49 {
 50 
 51    int T;
 52    cin>>T;
 53    for(int t=1;t<=T;t++)
 54    {
 55        memset(s1,'',sizeof(s1));
 56        memset(s2,'',sizeof(s2));
 57        memset(s12,'',sizeof(s12));
 58        memset(sans,'',sizeof(sans));
 59        mmap.clear();
 60 
 61        int c;
 62        cin>>c;
 63        for(int i=0;i<c;i++)
 64             cin>>s1[i];
 65        for(int i=0;i<c;i++)
 66             cin>>s2[i];
 67        for(int i=0;i<2*c;i++)
 68             cin>>sans[i];
 69 
 70         cout<<t<<" ";
 71         int time=1;
 72         int step=0;
 73         int ok=0;
 74 
 75         while(time++)
 76         {
 77             shuffle(s1,s2,s12);
 78             if(mmap[(string)s12]==true)
 79                 break;
 80             else
 81                 mmap[(string)s12]=true;
 82             step++;
 83 
 84             if(!strcmp(s12,sans))
 85             {
 86                 ok=1;
 87                 break;
 88             }
 89             else
 90                 split(s12,s1,s2);
 91         }
 92         if(!ok)
 93             cout<<-1<<endl;
 94         else
 95             cout<<step<<endl;
 96 
 97 
 98    }
 99 
100 
101 
102 
103    /*   //下面这些只是一个mmap插入的测试
104    char str1[]="abcde";
105    //string str=(string)str1;
106    int value=1;
107    for(int i=0;i<5;i++)
108    {
109        mmap.insert(pair<string,bool>(str1,true));
110        str1[0]='A'+value;
111        value++;
112    }
113 
114    for(map<string,bool>::iterator it=mmap.begin();it!=mmap.end();it++)
115    {
116        cout<<it->first<<"--"<<it->second<<endl;
117    }
118    */
119     return 0;
120 }
View Code

H - Pots

题意：有两个空水壶，pot1,pot2。操作有6种：

FILL(1):用水把pot1填满，

FILL(2):用水把pot2填满，

DROP(1):把pot1里的水全部倒掉，

DROP(2):把pot2的水全部倒掉，

POUR(1,2):把pot1里的水倒在pot2里，如果pot2能盛下，就全部倒过去，如果盛不下，把pot2倒满，pot1剩点。

POUR(2,1):同POUR(1,2)，只不过从pot2倒向pot1。

输入a,b,c。a,b分别表示pot1和pot2的容量，c表示要量出的体积(即怎样操作使pot1或者pot2中水的体积为c)，

输出操作步骤。

思路：用一个结构体记录pot1和pot2的状态，搜索即可。还是比较麻烦的，看代码。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <stack>
  7 #include <map>
  8 
  9 using namespace std;
 10 
 11 const int MAXN=150;
 12 
 13 string op[6]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"}; //6中操作
 14 
 15 int a,b,c;
 16 
 17 struct node   //这个结构体记录每步操作的信息。
 18 {
 19     int prex;  //上一个操作的x
 20     int prey;  //上一个操作的y
 21     int step;  //当前操作的步数
 22     int op;    //记录第几种操作
 23 }v[MAXN][MAXN];
 24 
 25 struct point   //记录pot1和pot2的状态
 26 {
 27     int x,y;
 28 };
 29 
 30 void dfs_print(int x,int y)   //递归输出 每种操作
 31 {
 32     if(x==0&&y==0)
 33         return;
 34     dfs_print(v[x][y].prex,v[x][y].prey);
 35 
 36     cout<<op[v[x][y].op]<<endl;
 37 
 38 }
 39 
 40 void bfs()
 41 {
 42     queue<point> Q;
 43     point s,q;
 44     s.x=s.y=0;  //初始化pot1,pot2为0
 45     v[0][0].step=1;
 46     Q.push(s);
 47 
 48     while(Q.size())
 49     {
 50         s=Q.front();
 51         Q.pop();
 52 
 53         if(s.x==c||s.y==c)  //如果达到目标体积输出
 54         {
 55             cout<<v[s.x][s.y].step-1<<endl;
 56             dfs_print(s.x,s.y);
 57             return;
 58         }
 59         for(int i=0;i<6;i++)  //6种操作
 60         {
 61             q=s;
 62             if(i==0)
 63                 q.x=a;
 64             else if(i==1)
 65                 q.y=b;
 66 
 67             else if(i==2)
 68                 q.x=0;
 69 
 70             else if(i==3)
 71                 q.y=0;
 72             else if(i==4)
 73             {
 74                 if(q.x<=b-q.y)
 75                 {
 76 
 77                     q.y+=q.x;q.x=0;
 78                 }
 79                 else
 80                 {
 81                     q.x-=(b-q.y);
 82                     q.y=b;
 83                 }
 84             }
 85             else
 86             {
 87                 if(q.y<=a-q.x)
 88                 {
 89 
 90                     q.x+=q.y;q.y=0;
 91                 }
 92                 else
 93                 {
 94 
 95                     q.y-=(a-q.x);q.x=a;
 96                 }
 97             }
 98             if(v[q.x][q.y].step==0)
 99             {
100                 v[q.x][q.y].step=v[s.x][s.y].step+1;
101                 v[q.x][q.y].op=i;
102                 v[q.x][q.y].prex=s.x;
103                 v[q.x][q.y].prey=s.y;
104                 Q.push(q);
105             }
106 
107 
108         }
109     }
110 
111     cout<<"impossible"<<endl;
112 
113 }
114 
115 int main()
116 {
117     while(cin>>a>>b>>c)
118     {
119         memset(v,0,sizeof(v));
120         bfs();
121     }
122 
123     return 0;
124 }
View Code

K - 迷宫问题

水题，直接贴代码。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 
 7 const int MAXN=5;
 8 
 9 int mapp[MAXN][MAXN];
10 
11 struct point
12 {
13     int x,y;
14 };
15 
16 struct vis
17 {
18     int prex,prey;
19     int step;
20 }v[MAXN][MAXN];   //记录路径
21 
22 void dfs(int x,int y)   //递归输出路径
23 {
24     if(x==0&&y==0)
25     {
26         printf("(%d, %d)
",x,y);
27         return;
28     }
29 
30     dfs(v[x][y].prex,v[x][y].prey);
31     printf("(%d, %d)
",x,y);
32 }
33 
34 void bfs()
35 {
36     queue<point> Q;
37     point s,q;
38     int dx[4]={1,-1,0,0};   //四个方向
39     int dy[4]={0,0,-1,1};
40     s.x=0;s.y=0;
41     v[s.x][s.y].step=1;
42     Q.push(s);
43     while(!Q.empty())
44     {
45         s=Q.front();
46         Q.pop();
47         if(s.x==4&&s.y==4)
48         {
49             dfs(s.x,s.y);
50         }
51         for(int i=0;i<4;i++)
52         {
53             q.x=s.x+dx[i];
54             q.y=s.y+dy[i];
55             if(q.x>=0&&q.x<5&&q.y>=0&&q.y<5&&!mapp[q.x][q.y]&&v[q.x][q.y].step==0)  //判断越界和是否访问过
56             {
57                 v[q.x][q.y].step=v[s.x][s.y].step+1;
58                 v[q.x][q.y].prex=s.x;
59                 v[q.x][q.y].prey=s.y;
60                 Q.push(q);
61             }
62         }
63 
64     }
65 
66 }
67 
68 int main()
69 {
70     memset(v,0,sizeof(v));
71     for(int i=0;i<5;i++)
72     {
73         for(int j=0;j<5;j++)
74         {
75             cin>>mapp[i][j];
76         }
77     }
78 
79     bfs();
80     return 0;
81 }
View Code

--------------------------------没了------------------------------------

人生如修仙，岂是一日间。何时登临顶，上善若水前。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/f-society/p/5711511.html