【6.28校内test】T1 Jelly的难题1

废话一句：今天中考出成绩，感觉大家考的都超级棒，不管怎样，愿大家成为最好的自己。

好了废话完了，下面是题解部分：

SOLUTION：

首先你可能发生的，是看不懂题：

定睛一看，这是个广搜！（然后非常幸运昨天刚做了一个广搜的题，然后我就会了）

首先先是输入部分，这个真的很毒瘤了，当sy已经去忙akT1的时候，我还在可怜的与读入作斗争（与读入抗争掉了大部分时间可还行）。读入很毒瘤，因为每个字符之间有空格，所以读入的时候要用while过滤。然后咱的读入好生毒瘤，看看就好啦（相信像ych这样的大佬肯定有更优的方法）：

n=read();m=read();

    char ch=getchar();

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            while(ch==' '||ch=='\n'||ch=='\r') ch=getchar();

            a1[i][j]=ch;

            if(a1[i][j]=='*') x=i,y=j,a[i][j]=;

            if(a1[i][j]=='#') a[i][j]=;

            if(a1[i][j]=='o') a[i][j]=;

            ch=getchar();

        }

    }

然后就是bfs部分了，其实就是一个标准的广搜板子，然后因为最近看了tarjan，我居然在bfs里用了时间戳可海星。

首先要说一直理解不了构造函数这种东西，所以一直都是写赋值函数，看看就好。

首先显然是把*（也就是打印机）的地方加进队列中，然后别忘记开vis记录已经走过了。

然后while(!q.empty())，每次取出队首，向四个方向扩展（当然前提是可以扩展因此记得写pan函数），然后对于最大时间以及卷子数量，我用了时间的理念，也就是记录访问顺序（当然并不是完全时间戳），进行储存与bfs，每次取出队首，然后四个方向尝试拓展，如果可以拓展，那么拓展，将其入队，并将新入队的结点的dfn值在被拓展出的结点的基础上+1，这样最大的dfn也就是最大的时间ans。然后还有如何算总共的卷子数，我的算法比较复杂，感觉过于麻烦了（看看就好啦），记录每个时间戳，然后用ans-时间戳+1，表示的就是这个结点的卷子数。然后加起来就好啦。

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=;

    char last,ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m,x,y;

int a[][];

int dx[]={,-,,};

int dy[]={,,-,};

char a1[][];

bool vis[][];

const int mod=;

struct node{

    int x,y,dfn;

};

node fz(int x,int y,int dfn){

    node rtn;

    rtn.x=x;

    rtn.y=y;

    rtn.dfn=dfn;

    return rtn;

}

bool pan(int x,int y){//判断函数，保证行走合法

    return x>=&&y>=&&x<=n&&y<=m&&vis[x][y]==&&a[x][y]==;

}

queue<node> q;

void bfs(){

    q.push(fz(x,y,));

    vis[x][y]=;

    int ans=,sum=;

    int cnt=,cz[];

    while(!q.empty()){

        node h=q.front();

        cz[++cnt]=h.dfn%mod;

        q.pop();

        for(int i=;i<;i++){

            int xx=h.x,yy=h.y,dfnn=h.dfn;

            if(pan(xx+dx[i],yy+dy[i])){

                xx+=dx[i];yy+=dy[i];

                q.push(fz(xx,yy,dfnn+));

                vis[xx][yy]=;

                if(dfnn+>ans) ans=dfnn+;

            }

        }

    }

    for(int i=;i<=cnt;i++)//我太菜了的求卷子数法qwq

      sum=(sum%mod+ans%mod-cz[i]%mod+)%mod;

    cout<<ans<<endl<<sum<<endl;

}

int main(){

    n=read();m=read();

    char ch=getchar();

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            while(ch==' '||ch=='\n'||ch=='\r') ch=getchar();

            a1[i][j]=ch;

            if(a1[i][j]=='*') x=i,y=j,a[i][j]=;

            if(a1[i][j]=='#') a[i][j]=;

            if(a1[i][j]=='o') a[i][j]=;

            ch=getchar();

        }

    }

    bfs();

    return ;

}

end-

巴特西

【6.28校内test】T1 Jelly的难题1

最新文章

热门文章