您的位置: 首页  >  IT文章  >  2014 UESTC暑前集训搜索专题解题报告

2014 UESTC暑前集训搜索专题解题报告

分类: IT文章 • 2024-08-30 13:32:01

A.解救小Q

BFS。每次到达一个状态时看是否是在传送阵的一点上，是则传送到另一点即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define NA 100007

char mp[52][52];

struct status
{
    int x,y;
    int l;
};

int vis[52][52];

struct transport
{
    int x1,y1;  //初始点
    int x2,y2;  //传送目标点
    int flag;
}a[27];

int n,m;
int head,tail;
int pathx[4]={0,1,0,-1};
int pathy[4]={-1,0,1,0};

bool OK(int nx,int ny)
{
    return nx>=0&&ny>=0&&nx<n&&ny<m;
}

int bfs(int x,int y)
{
    status now,next;
    queue<status> que;
    now.x=x;
    now.y=y;
    now.l=0;
    vis[now.x][now.y]=1;
    que.push(now);
    while(!que.empty())  //队列非空
    {
        now = que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int nx=now.x+pathx[i];
            int ny=now.y+pathy[i];
            if(vis[nx][ny] || !OK(nx,ny))
                continue;
            if(mp[nx][ny]=='Q')
                 return now.l+1;
            if(mp[nx][ny]!='#')
            {
                if(mp[nx][ny]>='a'&&mp[nx][ny]<='z')
                {
                    int h=mp[nx][ny]-'a';
                    if(a[h].x1!=nx||a[h].y1!=ny)  //初始点和目标点可以互换
                    {
                        next.x=a[h].x1;
                        next.y=a[h].y1;
                    }
                    else
                    {
                        next.x=a[h].x2;
                        next.y=a[h].y2;
                    }
                    next.l=now.l+1;
                    que.push(next);
                }
                else
                {
                    next.x=nx;
                    next.y=ny;
                    next.l=now.l+1;
                    que.push(next);
                }
                vis[nx][ny]=1;
            }
        }
    }
    return -1;
}

int main()
{
    int T,x,y;
    int N,M;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(mp,0,sizeof(mp));
        for(int j=0;j<27;j++)
            a[j].flag=0;
        scanf("%d%d",&N,&M);
        n=N;
        m=M;
        getchar();
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                scanf("%c",&mp[i][j]);
                if(mp[i][j]=='L')
                {
                    x=i;
                    y=j;
                }
                if(mp[i][j]>='a'&&mp[i][j]<='z')
                {
                    int h=mp[i][j]-'a';
                    if(a[h].flag==0)
                    {
                        a[h].x1=i;
                        a[h].y1=j;
                        a[h].flag=1;
                    }
                    else if(a[h].flag==1)
                    {
                        a[h].x2=i;
                        a[h].y2=j;
                    }
                }
            }
            getchar();
        }
        printf("%d
",bfs(x,y));
    }
    return 0;
}
View Code

B.方老师开橙卡

每次枚举一位数，从1位数字到9位数字，满足条件则加入队列。比如21，首先1*1 = 1 和 9*9 = 81 都满足个位与21的个位相同，加入队列，下次就考虑匹配第二位，然后第三位，。。每次去除相同位数的数字（que.size()），比如去除Y，则拓展的时候枚举X，这时m=10*X+Y，看此时m^2的那一位是否与n的那一位匹配，如果匹配，则加入队列。每次如果相等，顺便判断一下是否就是n，就是的话直接与答案相比，小于答案则更新答案。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 50007

int Scheck(ll ka,ll n)
{
    while(ka && n)
    {
        if(ka%10 != n%10)
            return 0;
        ka/=10;
        n/=10;
    }
    if(n == 0)
        return 1;
    else
        return 0;
}

ll Ten(int wei)
{
    ll res = 1;
    for(int i=0;i<wei;i++)
        res *= 10;
    return res;
}

ll toTen(ll tmp)
{
    ll res = 1;
    while(tmp)
    {
        res *= 10;
        tmp /= 10;
    }
    return res;
}

ll ans;
int w[12],ind;

void BFS(ll n)
{
    queue<ll> que;
    ll m,x,y;
    for(y=0;y<=9;y++)
    {
        ll ka = y*y;
        if(ka%10 == w[1])
        {
            if(Scheck(ka,n))
            {
                if(y < ans)
                    ans = y;
            }
            else
                que.push(y);
        }
    }
    int layer = 1;
    while(!que.empty())
    {
        layer++;
        if(layer > 10 || layer >= ind)
            return;
        ll ten = Ten(layer-1);
        int qsize = que.size();
        while(qsize--)
        {
            ll tmp = que.front();
            que.pop();
            for(x=0;x<=9;x++)
            {
                m = ten*x+tmp;
                ll m2 = m*m;
                if((m2/ten)%10 == w[layer])
                {
                    if(Scheck(m2,n))
                    {
                        if(m < ans)
                            ans = m;
                    }
                    else
                        que.push(m);
                }
            }
        }
    }
    return;
}

int main()
{
    int T;
    ll n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        if(n == 0)
        {
            printf("0
");
            continue;
        }
        ll kn = n;
        ind = 1;
        while(kn)
        {
            w[ind++] = kn%10;
            kn/=10;
        }
        ans = Mod;
        BFS(n);
        if(ans == Mod)
            puts("None");
        else
            printf("%lld
",ans);
    }
    return 0;
}
View Code

C.贪吃蛇

如果存储每节身体的坐标，会爆Memory的。

考虑因为每个相邻节的坐标都是相邻的，维护一个节与前一个节的关系即可，有四种情况，可以分别用00,01,10,11来表示，这样的话就只需维护蛇头的坐标，根据01关系就可推断出整个蛇身的位置。然后就是BFS了，注意不要咬到蛇身和往自己来的方向走（如果长度为1的话就可以）。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 107

struct Point
{
    int x,y;
}p[11];

struct node
{
    int x,y;
    int num,step;
}S;

char mp[17][17];
int vis[70000][16][16];
int R,C,K;
int EX,EY;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};

int p_to_num(Point *p)
{
    int i,k;
    int res = 0,now = 0;
    for(i=1;i<K;i++)
    {
        int sx = p[i].x;
        int sy = p[i].y;
        int tx = p[i+1].x;
        int ty = p[i+1].y;
        if(sx > tx && sy == ty)
            k = 3;   //下
        else if(sx == tx && sy > ty)
            k = 2;   //右
        else if(sx < tx && sy == ty)
            k = 0;   //上
        else if(sx == tx && sy < ty)
            k = 1;   //左
        k <<= now;
        now += 2;
        res |= k;
    }
    return res;
}

bool OK(int nx,int ny)
{
    if(nx >= 0 && nx < R && ny >= 0 && ny < C)
        return true;
    return false;
}

bool check(int num)
{
    int i,j,k;
    k = K-1;
    int x = 0,y = 0;
    while(k--)
    {
        x += dx[num&3];
        y += dy[num&3];
        if(x == 0 && y == 0)
            return false;
        num >>= 2;
    }
    return true;
}

int BFS(node S)
{
    int i,j,k;
    queue<node> que;
    memset(vis,0,sizeof(vis));
    que.push(S);
    vis[S.num][S.x][S.y] = 1;
    int MOD = (1<<((K-1)*2));
    while(!que.empty())
    {
        node tmp = que.front();
        que.pop();
        if(tmp.x == EX && tmp.y == EY)
            return tmp.step;
        for(i=0;i<4;i++)
        {
            if(K <= 1 || ((tmp.num&3) != i))
            {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if(!OK(nx,ny) || mp[nx][ny] == '#')
                    continue;
                node now;
                now.num = (tmp.num << 2);
                now.num |= (3-i);
                now.num %= MOD;
                if(vis[now.num][nx][ny])   //状态已走过
                    continue;
                if(!check(now.num))    //咬到蛇身
                    continue;
                vis[now.num][nx][ny] = 1;
                now.x = nx;
                now.y = ny;
                now.step = tmp.step + 1;
                que.push(now);
            }
        }
    }
    return -1;
}

int main()
{
    int i,j,k,cs = 1;
    while(scanf("%d%d",&R,&C)!=EOF)
    {
        K = 1;
        for(i=0;i<R;i++)
        {
            scanf("%s",mp[i]);
            for(j=0;j<C;j++)
            {
                if(mp[i][j] == '@')
                    EX = i,EY = j;
                if(mp[i][j] >= '1' && mp[i][j] <= '9')
                {
                    k = mp[i][j] - '0';
                    p[k].x = i,p[k].y = j;
                    K = max(K,k);
                }
            }
        }
        S.num = p_to_num(p);
        S.x = p[1].x;
        S.y = p[1].y;
        S.step = 0;
        printf("Case #%d: %d
",cs++,BFS(S));
    }
    return 0;
}
View Code

D.方老师与素数

BFS搜索。每次改变一位（千位，百位，十位或个位），拓展状态，直到达到目标状态。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 10007

int u[N],c,vis[N],prime[N];
int n,a,b,flag;
struct node
{
    int num,step;
}S,E;

void doit()
{
    int i,j;
    c=0;
    for(i=2;i<=10003;i++)
        u[i] = 1;
    for(i=2;i<=10003;i++)
    {
        if(u[i])
           prime[c++] = i;
        for(j=0;j<c&&i*prime[j]<=10003;j++)
        {
            u[i*prime[j]] = 0;
            if(i%prime[j] == 0)
               break;
        }
    }
}

int change(int base,int num,int ind)
{
    char ss[5];
    ss[0] = base/1000 + 48;
    ss[1] = (base/100)%10 + 48;
    ss[2] = (base/10)%10 + 48;
    ss[3] = base%10 + 48;
    ss[ind] = num + 48;
    ss[4] = '

相关推荐