[大题解]搜索五题

QingLin001 · 2020-11-20 09:50:49 · 个人记录

搜索五题

\quad\color{black}\text{P1332 血色先锋队}

\quad\color{black}\text{P3395 路障}

\quad\color{black}\text{P6207 [USACO06OCT] Cows on Skates G}

\quad\color{black}\text{P1238 走迷宫}

\quad\color{black}\text{P3956 棋盘}

难度：中等

题目分析

1.血色先锋队

给定一个大小为n\times m的矩阵A，有a个坐标为(x_i,y_i)的人，每一秒会将是否感染的状态传递给(up,down,left,right)的人。现在请你求出b个坐标为(X_i,Y_i)的人的感染时间。

2.路障

给定一个大小为n^2的矩阵A，一个人要从(1,1)走到(n,n)，期间的2n-2秒内，每一秒在(x_i,y_i)上会出现一个路障，求这个人是否能成功走到(n,n)。

3.[USACO06OCT] Cows on Skates G

给定一个大小为r\times c的矩阵A，一个人要从(1,1)走到(r,c)，其中若A_{i,j}的值是'.'，则可以通过，反之无法通过。请输出其中一种路径。

4.走迷宫

给定一个大小为m\times n的矩阵A，一个人要从(sx,sy)走到(tx,ty)，若A_{i,j}的值是1，则可以通过，反之无法通过。请输出所有的路径。

5.棋盘

给定一个大小为m^2的染色矩阵A，其中从有色走到有色但颜色不同的格子需要1点代价，从有色走到相同颜色的格子不需要代价，从有色走到无色的格子需要2点代价，且这种格子路过之后会还原成无色。求一个人从(1,1)走到(m,m)的最小代价；若无法到达，输出-1。

思路分析

1.血色先锋队

这题我们可以采用BFS的策略，将每个感染源（感染者）的坐标放入队列；当队列不空时，则说明没有全部感染。接着我们定义方向数组，向(up,down,left,right)的人进行传染，最后预处理出所有人的感染时间T[i][j]，在询问的时候输出相应的T[x][y]即可。

2.路障

这题我们也可以采用BFS的策略，将每个点的坐标(x,y)以及对应的走到的时间t放入队列（定义一个结构体）。接着我们将所有的路障下落时间提前存放到数组中，再在每个单位时间内将它标记。接着进行移动，更新即可。

3.[USACO06OCT] Cows on Skates G

这题我使用的算法是DFS。这题比较简单，而且数据范围非常人性。我们只需要常规跑DFS，但是要定一个答案数组ans[N][2]，ans[i][0]存放当前合法的x坐标，ans[i][1]存放当前合法的y坐标。最后当x==r且y==c时，从1到cnt依次输出ans[i][0],ans[i][1]即可。

4.走迷宫

这题我们还是可以常规DFS。思路和第三题差不多，只不过我们不用判断此时的x,y是否合法，因为如果超出边界，A[x][y]必然为0（而且如果加判断会神秘\tt{WA}掉）。接着和第三题都一样。

5.棋盘

依旧是DFS。直接定义一个d[N][N]数组，其中d[i][j]表示(1,1)->(i,j)的最小价值，是我们剪枝的依据。接着定义coin=0x7f7f7f7f，在dfs()中更新即可。最后如果coin==0x7f7f7f7f则说明走不到，输出-1，反之输出coin。

Code Share

1.血色先锋队

#include<bits/stdc++.h>
using namespace std;
const int N=555;
int ans[N][N];
int dx[]={0,0,0,-1,1},dy[]={0,1,-1,0,0};
int n,m,a,b;
bool v[N][N];
struct node{
    int x,y,t;
};
int main()
{
    queue<node> q;
    scanf("%d %d %d %d",&n,&m,&a,&b);
    while(a--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        node p;
        p.x=x,p.y=y,p.t=0;
        q.push(p);
        v[x][y]=1;
    }
    while(q.size())
    {
        node now=q.front();
        node p;
        for(int i=1;i<=4;i++)
        {
            now=q.front();
            int x=now.x,y=now.y,t=now.t;
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1 && xx<=n && yy>=1 && yy<=m && !v[xx][yy])
            {   
                v[xx][yy]=1;
                p.x=xx;
                p.y=yy;
                p.t=t+1;
                q.push(p);
            }
        }
        ans[now.x][now.y]=now.t;
        q.pop();
    } 
    while(b--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",ans[x][y]);
    } 
    return 0;
}

2.路障

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=2020;
int stopx[M],stopy[M];
int dx[]={0,0,0,-1,1},dy[]={0,1,-1,0,0};
int T;
struct node{
    int x,y,t;
};
bool v[N][N],v2[N][N];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++)
            scanf("%d %d",&stopx[i],&stopy[i]);
        memset(v,0,sizeof(v));
        memset(v2,0,sizeof(v2));
        //bfs
        v[1][1]=1;
        bool flag=0;
        queue<node> q;
        node p,l;
        p.x=1,p.y=1,p.t=0;
        q.push(p);
        while(q.size())
        {
            p=q.front();
            q.pop();
            int x=p.x;
            int y=p.y;
            int t=p.t;
            if(x==n && y==n)
            {
                flag=1;
                break;
            }
            v2[stopx[t]][stopy[t]]=1;
            for(int i=1;i<=4;i++)
            {
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(xx>=1 && xx<=n && yy>=1 && yy<=n && !v[xx][yy] &&!v2[xx][yy])
                {
                    l.x=xx;
                    l.y=yy;
                    l.t=t+1;
                    v[xx][yy]=1;
                    q.push(l);
                }
            }
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

3.[USACO06OCT] Cows on Skates G

#include<bits/stdc++.h>
using namespace std;
const int N=120,M=80;
int dx[]={0,0,0,-1,1};
int dy[]={0,-1,1,0,0};
int r,c,cnt=1,ans[100010][2];
bool v[N][M];
char a[N][M];
void dfs(int x,int y)
{
    if(x==r && y==c) 
    {
        for(int i=1;i<=cnt;i++)
            printf("%d %d\n",ans[i][0],ans[i][1]);
        return ;
    }
    for(int i=1;i<=4;i++) 
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1 && xx<=r && yy>=1 && yy<=c && !v[xx][yy] && a[xx][yy]=='.') 
        {
            v[xx][yy]=1;
            cnt++;
            ans[cnt][0]=xx;
            ans[cnt][1]=yy;
            dfs(xx,yy);
            cnt--;
        }
    }
}
int main()
{
    scanf("%d %d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        char s[N];
        scanf("%s",s+1);
        for(int j=1;j<=c;j++)
            a[i][j]=s[j];
    }
    ans[1][0]=ans[1][1]=1;
    v[1][1]=1;
    dfs(1,1);
    return 0;
}

4.走迷宫

#include<bits/stdc++.h>
using namespace std;
const int N=16;
int a[N][N],p[50050][2];
int dx[5]={0,0,-1,0,1};
int dy[5]={0,-1,0,1,0};
int m,n,cnt;
bool v[N][N],flag;
int sx,sy,tx,ty;
void dfs(int x,int y)
{
    if(x==tx && y==ty)
    {
        flag=1;
        for(int i=1;i<=cnt;i++)
            printf("(%d,%d)->",p[i][0],p[i][1]);
        printf("(%d,%d)\n",tx,ty);
        return ;
    }
    for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(!v[xx][yy] && a[xx][yy]==1)
        {
            ++cnt;
            v[x][y]=1;
            p[cnt][0]=x;
            p[cnt][1]=y;
            dfs(xx,yy);
            v[x][y]=0;
            --cnt;
        }
    }
}
int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d\n%d %d",&sx,&sy,&tx,&ty);
    dfs(sx,sy);
    if(flag==0)
    {
        printf("-1");
        return 0;
    }
    return 0;
}

5.棋盘

#include<bits/stdc++.h>
using namespace std;
const int M=101;
int a[M][M],n,m,coin=0x7f7f7f7f;
int color[M][M],d[M][M];
bool v[M][M];
int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
void dfs(int x,int y,int now,bool magic)
{
    if(x<1 || x>m || y<1 || y>m)
        return ;
    if(now>=d[x][y])
        return ;
    d[x][y]=now;
    if(x==m && y==m) //走到终点 
    {
        coin=min(coin,now);
        return ;
    }
    for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        //下一个格子有色 
        if(color[xx][yy])
        {
            if(color[xx][yy]!=color[x][y])
                dfs(xx,yy,now+1,false);
            else
                dfs(xx,yy,now,false);
        }
        //没有用魔法 
        else if(!magic)
        {
            color[xx][yy]=color[x][y];
            dfs(xx,yy,now+2,true);
            color[xx][yy]=0;
        }
    }
}
int main()
{
    memset(d,0x7f,sizeof(d));
    scanf("%d %d",&m,&n);
    //(1,1)->(m,m)
    for(int i=1;i<=n;i++)
    {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        color[x][y]=c+1;
        //c==0无色，c==1为红色，c==2为黄色 
                //小技巧：为了区分有色和无色
    }
    dfs(1,1,0,false);
    printf("%d",coin==0x7f7f7f7f ? -1:coin);
    return 0;   
}