景女神与她的托福（BFS+状压）

景女神与她的托福

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 49 Accepted Submission(s) : 21

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

景女神最近一直在恶补英语，她要为了她的托福做准备。于是，满神给景女神出了一道题，来帮助景女神学习英语。

满神给了景女神一个长度为n的字符串，字符串只包含小写字母 a,b;并且告诉景女神她最多可以改变k个字符(a->b, b->a);满神想知道经过不超过k次的改变后，出现相同字母的字符串(连续)的最大长度是多少。

景女神觉得这个题和她记单词并没有什么关系，于是就学英语去了。但是满神希望聪明的你可以帮助他解决这个问题。

Input

多组输入，每组输入如下

第一行输入两个整数n和k，用空格隔开 (1 <= n <= 100000, 0 <= k <= n);

第二行输入一个字符串。(只包含小写字母 a和b);

Output

多组输出，每组输出一个整数，表示经过不超过k次改变后，出现相同字符的最大字符串长度。

Sample Input

4 2

abba

8 1

aabaabaa

Sample Output

4

5

Hint:

第一组样例：可以得到 aaaa 或者 bbbb;最大长度为4;

第二组样例：可以得到 aaaaabaa 或者 aabaaaaa; 最大长度的字符串是 aaaaa，长度为5;

Author

NWUFengJun

分析

保证每个点在每个状态下都只走一次使结果最优。

注意到只有四把钥匙，那么将第\(i\)把钥匙视为\(1<<i\),用status存储

那么可以定义一个\(vis[status][x][y]\)记录当前点访问状态，接下来BFS即可

代码

/*

每个点在拥有相同钥匙（状态）下都只走一遍，这样可以最短

*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#define cpy(a,b) memcpy(a,b,sizeof(b))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int n,m,ans;

char s[1010][1010];

bool vis[16][1010][1010];

int dir[4][2]={0,1,1,0,0,-1,-1,0};

struct node

{

    int x,y,status,time;

    node(){};

    node(int xx,int yy,int s,int t){ x=xx,y=yy,status=s,time=t; };

}tmp;

int bfs(int sx,int sy)

{

    mem(vis,0);

    queue<node>q;

    q.push(node(sx,sy,0,0));

    while(!q.empty())

    {

        tmp=q.front();

        q.pop();

        for(int i=0;i<4;++i)

        {

            int x=tmp.x+dir[i][0],y=tmp.y+dir[i][1],status=tmp.status,time=tmp.time;

            if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]!='*'&&!vis[status][x][y])

            {

                if(s[x][y]>='1'&&s[x][y]<='4')

                {

                    int ret=s[x][y]-'1';

                    if(status&(1<<ret))

                    {

                        vis[status][x][y]=1;

                        q.push(node(x,y,status,time+1));

                    }

                }

                else if(s[x][y]>='5'&&s[x][y]<='8')

                {

                    int ret=s[x][y]-'5';

                    status|=(1<<ret);

                    vis[status][x][y]=1;

                    q.push(node(x,y,status,time+1));

                }

                else if(s[x][y]=='.')

                {

                    vis[status][x][y]=1;

                    q.push(node(x,y,status,time+1));

                }

                else if(s[x][y]=='#') return time+1;

            }

        }

    }

    return -1;

}

int main()

{

    int sx,sy;

    while(scanf("%d %d",&n,&m)==2)

    {

        R(i,0,n)

        {

            scanf("%s",&s[i]);

            R(j,0,m) if(s[i][j]=='0') { sx=i;sy=j;s[i][j]='.'; break; }

        }

        ans=bfs(sx,sy);

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

景女神与她的托福（BFS+状压）

分析

代码

最新文章

热门文章