ZOJ 2849【瞎暴力的搜索】

思路：

靠评测机抖一抖的思路：

拿个队列维护一下符合类型的可以搜索（指四周还存在可以遍历的点）的点。然后暴力搜索，所以问题来了，这个暴力搜索会大大地重复遍历次数。

DFS遍历图以前一直忽略重复，以为搜到打个标记复杂度就很棒棒了，其实还是有一堆重复。

这个思路的代码见第一份。

正解：

那么问题就很明显了，为了减少遍历次数，所以我们BFS，每次仅遍历附近四个，然后拿优先队列维护天数小的，类型小的，这样复杂度仅仅是多了个log，减少了很多重复遍历次数。

第一份代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <vector>

#include <map>

#include <queue>

using namespace std;

#define LL long long

const int INF = 0x3f3f3f3f;

const int N = 250010;

struct asd{

    int tp;

    int day;

    int x,y;

}q[N];

int num;

bool cmp(asd a,asd b){

    return a.tp<b.tp;

}

int cnt[N];

int n,m;

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

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

int ma[550][550];

int type[550][550];

queue<asd>que;

bool Judge(int x,int y)

{

    if(x<0||y<0||x>=n||y>=m) return false;

    return true;

}

bool Check(int x,int y)

{

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

        int xx=x+dx[i];

        int yy=y+dy[i];

        if(Judge(xx,yy)){

            if(type[xx][yy]==-1) return true;

        }

    }

    return false;

}

void init()

{

    num=0;

    while(!que.empty()) que.pop();

    memset(type,-1,sizeof(type));

    memset(cnt,0,sizeof(cnt));

}

void DFS(asd now){

    asd nex;

    bool flag=false;

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

        int xx=now.x+dx[i];

        int yy=now.y+dy[i];

        if(!Judge(xx,yy)) continue;

        if(type[xx][yy]!=-1) continue;

        if(abs(ma[xx][yy])>now.day)

        {

            if(!flag){

                nex=now;

                nex.day=now.day+1;

                que.push(nex);

                flag=true;

            }

            continue;

        }

        type[xx][yy]=now.tp;

        nex.day=now.day;

        nex.x=xx;nex.y=yy;

        nex.tp=now.tp;

        DFS(nex);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

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

        {

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

            {

                scanf("%d",&ma[i][j]);

                if(ma[i][j]>0){

                    type[i][j]=ma[i][j];

                    q[num].day=1;

                    q[num].tp=ma[i][j];

                    q[num].x=i;

                    q[num].y=j;

                    num++;

                }

            }

        }

        sort(q,q+num,cmp);

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

        {

            if(Check(q[i].x,q[i].y))

                que.push(q[i]);

        }

        asd now;

        while(!que.empty())

        {

            now=que.front();que.pop();

            DFS(now);

        }

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

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

                cnt[type[i][j]]++;

        int qq,x;

        scanf("%d",&qq);

        while(qq--){

            scanf("%d",&x);

            printf("%d\n",cnt[x]);

        }

    }

    return 0;

}

第二份正解：百度一堆都是一样的吧。

巴特西

ZOJ 2849【瞎暴力的搜索】

最新文章

热门文章