搜索_C/C++/C#

搜索写在前面的话：

其实就是一些写题过程中遇到的很离谱的问题

全局变量与局部变量的关系及应用

利用好全局变量可以使我们的函数调用更加方便，因为调用函数的过程中会改变全局变量，从而在主函数中我们也能得到变化后的值，可以不用在函数体中引用。但是由此也会衍生出很多问题，比如不注意全局与局部的区别或者说在全局变量的基础上，在主函数内又定义了同名变量，那么主函数内的变量将会覆盖（？）全局变量，比如，在外部函数中调用了这个局部变量，返回到主函数中时你理所当然的以为经过这个函数后这个值已经变为你的目的值，然鹅，你得到的却是你在主函数中重复声明的这个变量的值！！！而且这个 b u g bug bug还很难发现！！！（至少对于我来说QAQ）因为在实现外部函数的时候，只改变了全局变量，主函数内定义的变量他找不到呀！除非你在函数参数内取主函数内的变量的地址，（如果只在主函数内声明了一次变量名，因为我在写这句话的过程中突然意识到，如果一个变量同时被全局和局部定义，那传入函数参数的地址是所在的局部变量的地址还是全局变量的地址呢？？？）如果你只在…思路被打断了。。。不啰嗦了。。。

是什么品种的憨憨总是记不全搜索的几大条件呢？？？判断是否越界，是否访问过，是否当前所在位置可走。。。
访问过要及时做好标记！！！
有的图要注意存点的时候的开的空间大小
有的数组要记得清空，尤其是多组数据的那种
要注意题目中给出的行数和列数，与变量名的对应关系，和行数列数是否一致 n , m n,m n,m r , c r,c r,c 看清先说的行还是列呀！！！
怎么还会有憨憨总是忘记 p o p pop pop 啊？？？？？！！！！
待补充。。。（踩了坑再来

BFS Flood Fill模型例题：池塘计数

(DFS乱入)

#include 
using namespace std;

const int N = 1e3+10;
int vis[N],cnt;
char g[N][N];
int n,m;
const int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};

void dfs(int x, int y)
{
    g[x][y]='.';
    for(int i = 0; i < 8; i++)
    {
        int a = x + dx[i],b = y + dy[i];
        if(g[a][b]=='W') dfs(a,b);
    }
}
int main()
{
    cin >> n >> m;
    for(int i=0;i> g[i];
    for(int i=0;i
            if (g[i][j] == 'W') 
            {
                dfs(i, j);
                cnt++;
            }
        }
    cout << cnt << endl;
    return 0;
}

BFS做法：

#include 
#include 
using namespace std;
#define x first
#define y second

const int N = 1010, M = N*N;
typedef pair PII;
int n, m, cnt;
char g[N][N];
int vis[N][N];
PII p[M];//!这里开始的大小是N 后来才意识到不够！只是数据比较水过了

void bfs(PII p)
{
    queueq;
    q.push(p);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = t.x-1; i <= t.x + 1; i++)
            for(int j = t.y - 1; j <= t.y + 1; j++)
            {
                if(!vis[i][j]&&i>=0&&i=0&&j
                    vis[i][j] = 1;
                    q.push({i,j});
                }
            }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> g[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(!vis[i][j]&&g[i][j] == 'W')
            {
                vis[i][j]=1;
                bfs({i,j});
                cnt++;
            }
        }
    cout << cnt << endl;
    return 0;
}

注意！：图的边长是 N N N,那存点要开 N ∗ N N*N N∗N的大小！！

这里在图论中要格外注意！！！

例题：城堡问题

#include 
#include 
using namespace std;
#define x first
#define y second
const int N = 60, M = N * N;
int m,n;

int g[N][N];
int vis[N][N];
typedef pair PII;
PII p[M];//存点的位置

int bfs(int x, int y)
{
    int area=0;
    queueq;
    q.push({x, y});
    vis[x][y]=1;
    while(q.size())
    {
        int dx[]={0,-1,0,1},dy[]={-1,0,1,0};//与每一位上的数字息息相关
        auto t = q.front();
        area++;
        q.pop();
        int tmp = g[t.x][t.y];
        for(int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i],b = t.y + dy[i];
            if(!((tmp>>i)&1)&&!vis[a][b] && a >= 0 && a < m && b >=0 && b < n )
            {
                vis[a][b]=1;
                q.push({a,b});
            }
        }
    }
    return area;
}
int main()
{
    cin >> m >> n;
    int cnt = 0, area = 0;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)       
            cin >> g[i][j];
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
        {
            if(!vis[i][j])
            {
                //area=0;绝对不可以！！！！每次都会与0作比较啊
                area = max(area, bfs(i, j));
                cnt++;
            }
        }     
    cout << cnt << endl << area << endl;
    return 0;
}

又踩坑了！！！QAQ

全局变量与局部变量！我真的会谢。。。

当我把 a r e a area area定义为全局变量。。。在每次 B F S BFS BFS中都会把 a r e a area area变为0，然后在主函数里就会每次与0比较取最大值。。。

另外，主函数里的变量名与外部函数中的函数名好像不冲突？

外部函数中的 a r e a area area只在执行那个函数的时候起作用，在主函数中是以函数返回值存在的。

例题：山峰和山谷

#include 
#include 
#define x first
#define y second
using namespace std;

const int N = 1010, M = N * N;

int n;
int g[N][N], vis[N][N];
typedef pair PII;

void bfs(PII p, bool &has_higher, bool &has_lower)
{
    queue q;
    q.push(p);
    vis[p.x][p.y]=1;
    //cout << "p.x p.y " << p.x << ' ' << p.y << endl; 
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int a = t.x, b = t.y;
        //cout << "a b " << a << ' ' << b << endl;
        //vis[t.x][t.y]=1;
        for(int i = t.x - 1; i <= t.x + 1; i++)
            for(int j = t.y - 1; j <= t.y + 1; j++)
            {
                if(i >= 0 && i < n &&j >= 0 && j < n )
                {
                    if(g[i][j] != g[a][b])
                    {
                        //cout << "g[i][j]!=g[a][b]n";
                        if(g[i][j] > g[a][b]) has_higher = true;
                        else has_lower = true;
                    }
                    else if(!vis[i][j])
                    {
                        //cout << "!visn";
                        q.push({i, j});
                        vis[i][j]=1;
                    }
                }
            }
    }
}
int main()
{
    cin >> n;
    
    for(int i=0;i> g[i][j];
    int peak=0,valley=0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            if(!vis[i][j])
            {
                bool has_higher=false,has_lower=false;
                bfs({i,j},has_higher,has_lower);
                if(!has_lower) valley++;
                if(!has_higher) peak++;
            }
        }
    cout << peak << ' ' << valley ;
    return 0;
}

无语啊！！！调 b u g bug bug调了好久！！！

还是太菜了QAQ

后来发现标记访问过没标记上，才发现是标记从 a , b a,b a,b点延伸出来的点而不是这俩点，同时把延伸出来的点在进队的同时标记为访问过，脑袋不在线，竟然还在出队的时候标记？？？

同时，调用几个函数的时候要记得引用 b o o l bool bool变量的地址，否则主函数内还是不受影响的。。。

然后是，这是一个边搜索便判断的过程，从一个未标记的点往外扩散，遇到相同高度的点就加入集合表示是同一类，遇到不同高度的就与集合中的高度比较，从而判断集合属于什么类型。

最短路模型例题：迷宫问题

#include 
#include 
#include 
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 1010;
int n;
int g[N][N];
PII pre[N][N];
const int dx[]={0,1,0,-1},dy[]={-1,0,1,0};
void bfs(int x, int y)
{
    queueq;
    q.push({x, y});
    pre[x][y]={0, 0};//感觉这里的赋值无实际意义，只是为了表示更新过了不能再遍历这里了
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < n && !g[a][b] && pre[a][b].x == -1)
            {
                q.push({a,b});
                pre[a][b] = {t.x, t.y};
            }
        }
    }
}
int main()
{
    cin >> n;
    memset(pre, -1, sizeof pre);
    for(int i = 0;i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> g[i][j];
    bfs(n - 1, n - 1);
    PII end = {0, 0};
    while(true)
    {   
        cout << end.x << ' ' << end.y << endl;
        if(end.x == n - 1 && end.y == n - 1) break;
        
        end = pre[end.x][end.y];
    }
    return 0;
}

感觉这题多了路径输出还是麻烦了不少的。。。

因为我们要记录最短路径并输出，而且还是从起点到终点，想象一下如果我们从起点搜到终点，那么保留的是上一步的路径，（这时我突然想到一个问题，为什么不能让他保存下一步的路径呢？！），但是如果我们从终点到起点搜索，那么保存的也是上一步的路径，但是这里的上一步，对于我们正向输出的时候就是下一步了。。。比如： ( 0 , 0 ) (0,0) (0,0)这个点是从 ( 1 , 0 ) (1,0) (1,0)转移过来的，也就是 ( 0 , 0 ) (0,0) (0,0)的 p r e pre pre是 ( 1.0 ) (1.0) (1.0)，但是我们正向看的话就是保存的是下一步的路径了。

w h i l e while while循环里的 p r e pre pre改成 n e x t next next就很好理解了，因为这里的 p r e pre pre就相当于 n e x t next next。

（感觉这里的 p r e pre pre数组和静态链表的 n e ne ne数组真的很像！）

还有！这里的 P I I PII PII类型的数组我没想到！！

例题：武士风度的牛

#include 
#include 
#include 
using namespace std;
#define x first
#define y second
const int N = 160, M = N * N;

int dist[N][N];
char g[N][N];
int n,m;
typedef pair PII;
queue q;
const int dx[]={-2,-2,-1,1,2,2,1,-1},
          dy[]={-1,1,2,2,1,-1,-2,-2};
int bfs()
{
    auto t = q.front();
    dist[t.x][t.y]=0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        if(g[t.x][t.y] == 'H') return dist[t.x][t.y];
        for(int i = 0; i < 8; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a >= 0 && a < m && b >=0 && b < n && g[a][b] != '*' && dist[a][b] == -1)
            {   //下面计算的包括到达终点的情况也就是为'H'，如果是则从上一步步数+1 入队，从队中取出时如果是终点直接返回该店所对应的dist
                //或者在下面直接判断终点，如果是终点则直接返回上一步的dist + 1
                dist[a][b]= dist[t.x][t.y] + 1;
                q.push({a, b});
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(dist, -1, sizeof dist);
    
    for(int i = 0; i < m; i++) 
        cin >> g[i];
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
        {
            if(g[i][j]=='K')
                q.push({i, j});
        }
    cout << bfs() << endl;
    return 0;
}

注意行数和列数的对应关系！！！

例题：抓住那头牛

#include 
#include 
#include 
#include 

using namespace std;
const int N = 2e5+10;//注意范围！！！
int dist[N],n,k;

int bfs()
{
    queueq;
    q.push(n);
    dist[n]=0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        if(t==k) return dist[t];
        if(t + 1 > 0 && t + 1 < N && dist[t + 1] == -1)
        {
            dist[t + 1] = dist[t] + 1;
            q.push(t + 1);
        }
        if(t - 1 >=0 && t - 1 < N && dist[t - 1] == -1)
        {
            dist[t - 1] = dist[t] + 1;
            q.push(t - 1);
        }
        if(t << 1 > 0 && t << 1 < N && dist[t << 1] == -1)
        {
            dist[t << 1] = dist[t] + 1;
            q.push(t << 1);
        }
    }
    return -1;
}
int main()
{
    cin >> n >> k;
    memset(dist, -1, sizeof dist);
    cout << bfs() << endl;
    return 0;
}

题目第一个需要注意的点是：数据范围

起点和终点的范围是 [ 0 , 1 0 5 ] [0,10^5] [0,105]，但因为操作的特殊性，使得当前所在的区间不一定就完全位于这个区间内，所以我们的区间要开大，可证明开到两倍是完全足够的（甚至还有点超）。

开始不理解为啥用 b f s bfs bfs求出的就是最短的时间（也就是移动的最少次数）

我的理解是：可以把这三种走的方式看作三个扩展的方向，一旦扩展到终点就停止，函数返回此时移动的次数，由于我们往三个方向的扩展是同时的，所以一旦有一个方向扩展到了终点，就停止了，（其实就相当于是在每一步枚举这三种操作的结果，如果结果合法，就将其入队，作为下一次枚举的初始状态，直到找到终点），因为一遇到终点就停止搜索，所以此时所移动的次数就是最少的。

确实是 b f s bfs bfs的一种特别的应用捏~

也想过用 d f s dfs dfs做，但最短路问题还是优先选择用 b f s bfs bfs吧，同时这个题目的数据范围有点大，用 d f s dfs dfs担心会爆栈。

多源BFS 例题：矩阵距离

#include 
#include 
#include 
using namespace std;
#define x first
#define y second

const int N = 1010;
typedef pair PII;
int dist[N][N];
int n,m;
char g[N][N];
queueq;
int cnt=0;
void bfs()
{
    int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
    
    while(q.size())
    {
        //cout << "pushn";
        auto t = q.front();
        //cout << t.x << ' ' << t.y << endl;
        q.pop();
        
        //cout << ++cnt << endl;
        for(int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            //cout << ++n << endl;
            if(a >= 0 && a < n && b >=0 && b < m && dist[a][b] == -1)
            {
                //cout << "updaten";
                dist[a][b] = dist[t.x][t.y] + 1;
                q.push({a, b});
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(dist, -1, sizeof dist);
    for(int i = 0; i < n; i++)
        cin >> g[i];
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == '1')
            {
                q.push({i, j});
                //cout << "q.size = " << q.size() << endl;
                dist[i][j]=0;
            }
        }
    bfs();
    //cout << "after bfsn";
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << dist[i][j] << ' ';
        puts("");
    }
    return 0;
}

开始不太懂原理，后来自己画了画图，模拟了样例秒懂了！

（因为感觉这样求出的不是对于每个点都是最短路，但其实是的，逻辑也很简单）

我们的做法是将所有起点先入队，然后对这些起点进行扩展，每次往外扩展都是一层层的，并且每次往外扩展到的都是最短距离，所以在此基础上再次扩展的也一定是最小距离，有点类似于… D i j k s t r a Dijkstra Dijkstra?

DFS D F S DFS DFS踩坑的教训：

标记数组 v i s [ ] vis[] vis[]要记得，如果有多组数据记得每次清空
同时，如果有多组数据，计数器要记得清零
d f s dfs dfs条件不要遗漏：比如！ v i s [ ] = = 0 vis[]==0 vis[]==0，在边界以内，符合题意，如可以走的位置才能走，特殊点如起点和终点，要不要计入步数或者能不能走，
… dots …

DFS之连通性模型

例题：迷宫

#include 
#include 

using namespace std;

const int N = 110;
int n;
char g[N][N];
int vis[N][N];
int xa,ya,xb,yb;
const int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};

bool dfs(int a,int b)
{
    if(g[a][b]=='#') return 0;//顺序的重要性 就算到达终点但终点是'#'也是不行的
    if(a==xb&&b==yb) return 1;
    vis[a][b]=1;
    for(int i=0;i<4;i++){
        int dx=a+dir[i][0],dy=b+dir[i][1];
        if(!vis[dx][dy]&&dx>=0&&dx=0&&dy
            if(dfs(dx,dy)) return 1;
            //vis[a][b]=0;
        }
        
    }
    return 0;
}
int main()
{
    int t; cin >> t;
    while(t--)
    {
        memset(vis,0,sizeof vis);
        cin >> n;
        for(int i=0;i> g[i];
        cin >> xa >> ya >> xb >> yb;
        if(dfs(xa,ya)) puts("YES");
        else puts("NO");
    }
    return 0;
}

例题：红与黑

#include 
#include 
#include 

using namespace std;

const int N = 30;

char g[N][N];
int vis[N][N],cnt;
int n,m;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!vis[a][b]&&a>=0&&a=0&&b
            cnt++;
            dfs(a,b);
        }
    }
}
int main()
{
    while(cin >> n >> m && n)
    {
        int x,y;
        cnt=0;
        memset(vis,0,sizeof vis);
        for(int i=0;i
                cin >> g[i][j];
                if(g[i][j]=='@') x=i,y=j;
            }
        dfs(x,y);        
        cout << cnt+1 << endl;
    }
    return 0;
}

开始条件不充分，忘记考虑边界条件，也没有清空标记数组，怪不得几个测试样例输出的数越来越小。。。

写法二：

#include 
#include 
#include 

using namespace std;

const int N = 30;

char g[N][N];
int vis[N][N];
int n,m;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

int dfs(int x,int y)
{
    vis[x][y]=1;
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!vis[a][b]&&a>=0&&a=0&&b

            cnt+=dfs(a,b);
        }
    }
    return cnt;
}
int main()
{
    while(cin >> n >> m && n)
    {
        int x,y;
        memset(vis,0,sizeof vis);
        for(int i=0;i
                cin >> g[i][j];
                if(g[i][j]=='@') x=i,y=j;
            }
        
        cout << dfs(x,y) << endl;
    }
    return 0;
}

一开始有点点懵，但之后顿悟，不就是找到满足条件的就加一嘛（只有满足条件的才能进行 d f s dfs dfs，才有返回值，返回值就是 1 1 1,每次加一。

DFS之搜索顺序

例题：马走日

#include 
#include 
using namespace std;

const int N = 10;
int ans;
int n,m,x,y;
bool vis[N][N];
const int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};

void dfs(int x,int y,int cnt)
{
    if(cnt==n*m){
        ans++;
        return;
    }
    vis[x][y]=1;
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a=0&&b
            dfs(a,b,cnt+1);
        }
    }
    vis[x][y]=0;
}
int main()
{
    int t; cin >> t;
    while(t--)
    {
        ans=0;
        cin >> n >> m >> x >> y;
        dfs(x,y,1);
        cout << ans << endl;
    }
    
}

d f s dfs dfs函数里加了一个变量记录走过的步数，另外要记住多组数据计数器要清空！！！

这里标记数组不清空没关系，因为在 d f s dfs dfs过程中会回溯，我们在这个过程中将标记恢复原样了！

例题：单词接龙

（这题竟然难度是简单！）

#include 
#include 

using namespace std;

const int N = 21;
int ans;
string word[N];
int rep[N][N],used[N];
int n;
void dfs(string dragon,int last)
{
    ans=max((int)dragon.size(),ans);
    used[last]++;
    for(int i=0;i
        if(rep[last][i]&&used[i]<2){
            dfs(dragon+word[i].substr(rep[last][i]),i);
        }
    }
    used[last]--;
}
int main()
{
    cin >> n;
    char st;
    for(int i=0;i> word[i];
    cin >> st;
    for(int i=0;i
            string a=word[i],b=word[j];
            for(int k=1;k
                if(a.substr(a.size()-k)==b.substr(0,k)){
                    rep[i][j]=k;//第i个后缀与第j个前缀的重合字母个数
                    break;//找最短的重合部分使串最长
                }
            }
        }
    for(int i=0;i
        if(word[i][0]==st){
            dfs(word[i],i);
        }
    }
    cout << ans << endl;
    return 0;
}

（感觉是实现不好想）

等有时间再做一遍~~（5月32号）~~

这里的 u s e d [ ] used[] used[]相当于标记数组，但不是只是标记那么简单了，要看数量，回溯的时候恢复现场就是把 u s e d [ ] used[] used[]次数减一。

还有个小细节是

m a x ( ) max() max()函数只能比较两个 i n t int int型， s . s i z e ( ) s.size() s.size()虽然看起来也是整形（？），但是还是要强制类型转换成 ( i n t ) (int) (int)！好像找到了之前奇奇怪怪的编译错误原因。。。

搜索

C/C++/C#相关栏目本月热门文章