Power oj 2545: Lovestring（稍复杂BFS）

搜索

题面链接

• 题意

在一个n*m的矩阵里从（1，1）走到（n，m），要求这条路径中存在一个lovestring，并且保证所走的路程最少。

• 样例

3 4 4//(1<=N,M,K<=100)
LOVE
ABC#
EFGH
LOVE//长度为k的lovestring字符串

1 2 10
AA
AAAAAAAAAA

• 分析

在很多种状态中我可以选择选或者不选这种状态，所以都是应该加入队列的。

• 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,z,i,j,l;
char mp[111][111],s[111];
int vis[111][111][111];//表示在x,y点所获得的lovestring的长度z。
int dir[4][2]={0,1,0,-1,1,0,-1,0};
struct node
{
    int x,y,z;//表示到(x,y)点所构成的love字符串的长度为z
};
int BFS()
{
    queue<node>q;
    node now,next;
    now.x=1;
    now.y=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=0;l<=k;l++)
                vis[i][j][l]=INT_MAX;
    if(mp[1][1]==s[1])
    {
        now.z=1;
        vis[1][1][1]=0;
    }
    else
    {
        now.z=0;
        vis[1][1][0]=0;
    }
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        //printf("%c\n",mp[now.x][now.y]);
        q.pop();
        if(now.x==n&&now.y==m&&now.z==k)
            return vis[n][m][k];
        for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>m||mp[next.x][next.y]=='#')
                continue;
            if(now.z==k)//已经遇到一个完整的字符串了
            {
                next.z=k;
                if(vis[next.x][next.y][k]>vis[now.x][now.y][k]+1)
                {
                    vis[next.x][next.y][k]=vis[now.x][now.y][k]+1;
                    q.push(next);
                }
            }
            else
            {
                if(mp[next.x][next.y]==s[1])//能构成love字符串首位
                {
                    next.z=1;
                    if(vis[next.x][next.y][1]>vis[now.x][now.y][now.z]+1)
                    {
                        vis[next.x][next.y][1]=vis[now.x][now.y][now.z]+1;
                        q.push(next);
                    }
                }
                if(now.z!=0)//前面有一部分字符串出现
                {
                    if(mp[next.x][next.y]==s[now.z+1])//能继续构成love字符串
                    {
                        next.z=now.z+1;
                        if(vis[next.x][next.y][next.z]>vis[now.x][now.y][now.z]+1)
                        {
                            vis[next.x][next.y][next.z]=vis[now.x][now.y][now.z]+1;
                            q.push(next);
                        }
                    }
                    else
                    {
                        next.z=0;
                        if(vis[next.x][next.y][0]>vis[now.x][now.y][now.z]+1)
                        {
                            vis[next.x][next.y][0]=vis[now.x][now.y][now.z]+1;
                            q.push(next);
                        }
                    }
                }
                else
                {
                    next.z=0;
                    if(vis[next.x][next.y][next.z]>vis[now.x][now.y][now.z]+1)
                    {
                        vis[next.x][next.y][next.z]=vis[now.x][now.y][now.z]+1;
                        q.push(next);
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++)
            scanf("%s",mp[i]+1);
        scanf("%s",s+1);
        int ans=BFS();
        printf("%d\n",ans);
    }
    return 0;
}