首页 > 搜索 > BFS搜索 > HDU 4225-Simulation?-BFS-[解题报告]HOJ
2015
05-23

HDU 4225-Simulation?-BFS-[解题报告]HOJ

Simulation?

问题描述 :

A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system. Computer simulations have become a useful part of mathematical modeling of many natural systems in physics, astrophysics, chemistry and biology, human systems in economics, psychology, social science, and engineering, of course, also computer.
“Fundamentals of compiling” is an important course for computer science students. In this course, most of us are asked to write a compiler to simulate how a programming language executes. Today, boring iSea invites a new programming language, whose name is Abnormal Cute Micro (ACM) language, and, YOU are assigned the task to write a compiler for it.
ACM language only contains two kinds of variables and a few kinds of operations or functions, and here are some BNF-like rules for ACM.
Enumeration?

Enumeration?

Enumeration?

Also, here is some explanation for these rules:
1) In ACM expressions, use exactly one blank to separate variables and operators, and as the rule indicates, the operator should apply right to left, for example, the result of “1 – 2 – 3" should be 2.
2) In the build function, use exactly one blank to separate integers, too.
3) Beside there are brackets in function, no other bracket exists.
4) All the variables are conformable, and never exceed 10000.
Given an ACM expression, your task is output its value. If the result is a integer, just report it, otherwise report an array using the format “{integer_0, integer_1, … , integer_n}”.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes a string indicating an valid ACM expression you have to process.

Technical Specification
1. 1 <= T <= 100
2. 1 <= |S| <= 100, |S| indicating the length of the string.

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes a string indicating an valid ACM expression you have to process.

Technical Specification
1. 1 <= T <= 100
2. 1 <= |S| <= 100, |S| indicating the length of the string.

样例输入:

10
1 + 1
1 - 2 - 3
dance(3)
vary(2) * 2
vary(sum(dance(5) - 1))
dance(dance(-3))
1 - 2 - 3 * vary(dull(build(1 2 3)))
dance(dance(dance(dance(dance(2)))))
sum(vary(100)) - sum(build(3038))
build(sum(vary(2)) dull(build(1 0)) 2 dull(dance(2))) - build(1 1 1 1)

样例输出:

Case 1: 2
Case 2: 2
Case 3: {3, -2, 1}
Case 4: {2, 4}
Case 5: {2, 1}
Case 6: -4
Case 7: {2, 5}
Case 8: {4, -3, 2, -1}
Case 9: 2012
Case 10: {2, 0, 1, 2}

题意:按照一定规律排列的蛇形矩阵中,从一个合数到上下左右相邻的合数要一步,但是如果某网格中是素数,

      则不能到该网格,给定两个合数,求从第一个到第二个最少要多少步。

链接:hdu 4225

#include<cstdio>
#include<cstring>
#include<queue>
#define N 110                 //N要开的稍微大点,我开成100错了、、、
using namespace std;
struct stu
{
    int x,y;
}p[N*N+10];
int a[N+10][N+10],pri[N*N+10]={1,1,0},s[N+10][N+10];
void sxjz()                 //构造符合题意的矩阵
{
    int i=0,j=0,t=N*N;
    memset(a,0,sizeof(a));
    while(t>0){
        while(j<N&&!a[i][j]){
            p[t].x=i;
            p[t].y=j;
            a[i][j++]=t--;
        }
        j--;
        i++;
        while(i<N&&!a[i][j]){
            p[t].x=i;
            p[t].y=j;
            a[i++][j]=t--;
        }
        i--;
        j--;
        while(j>=0&&!a[i][j]){
            p[t].x=i;
            p[t].y=j;
            a[i][j--]=t--;
        }
        j++;
        i--;
        while(i>=0&&!a[i][j]){
            p[t].x=i;
            p[t].y=j;
            a[i--][j]=t--;
        }
        i++;
        j++;
    }
}
void prime()               //筛选法求素数
{
    int i,j;
    for(i=2;i<=N*N;i++)
        if(pri[i]==0)
            for(j=i+i;j<=N*N;j+=i)
                pri[j]=1;
}
int bfs(int m,int n)
{
    int i,j;
    struct stu t;
    queue<struct stu> q;
    q.push(p[m]);
    s[p[m].x][p[m].y]=1;
    while(!q.empty()){
        t=q.front();
        q.pop();
        i=t.x;
        j=t.y;
        if(a[i][j]==n)
            return s[i][j]-1;
        if(i<N-1&&pri[a[i+1][j]]&&!s[i+1][j]){
            t.x=i+1;
            t.y=j;
            q.push(t);
            s[i+1][j]=s[i][j]+1;
        }
        if(i>0&&pri[a[i-1][j]]&&!s[i-1][j]){
            t.x=i-1;
            t.y=j;
            q.push(t);
            s[i-1][j]=s[i][j]+1;
        }
        if(j<N-1&&pri[a[i][j+1]]&&!s[i][j+1]){
            t.x=i;
            t.y=j+1;
            q.push(t);
            s[i][j+1]=s[i][j]+1;
        }
        if(j>0&&pri[a[i][j-1]]&&!s[i][j-1]){
            t.x=i;
            t.y=j-1;
            q.push(t);
            s[i][j-1]=s[i][j]+1;
        }
    }
    return -1;
}
int main()
{
    int m,n,k=0,t;
    prime();
    sxjz();
    while(scanf("%d%d",&m,&n)!=EOF){
        k++;
        memset(s,0,sizeof(s));
        t=bfs(m,n);
        if(t!=-1)
            printf("Case %d: %d\n",k,t);
        else
            printf("Case %d: impossible\n",k);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_code/article/details/37873753