首页 > 其他 > 详细

hdu 6253 (bfs打表)

时间:2018-10-19 13:39:46      阅读:130      评论:0      收藏:0      [点我收藏+]

链接:http://acm.hdu.edu.cn/showproblem.php?pid=6253

题意:

马可以往一个方向走两步,然后转个弯走一步,这样算一次动作,求问马n次动作后,能到达多少个点,重复到达的点只算一次。

思路:

一开始完全没思路,画图找了半天把自己画崩了,后面看到数据和样例感觉这应该是一道公式题,然后打了一个表。。

打表代码:

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long

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

int dx[] = {2,2,-2,-2,1,1,-1,-1};
int dy[] = {1,-1,1,-1,2,-2,2,-2};
int ans[10000],vis[1000][1000];
void bfs(){
    node now;
    queue<node>q;
    now.x = 500,now.y = 500,now.step = 0;
    ans[0] = 1;
    vis[500][500] = 1;
    q.push(now);
    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(now.step == 20) continue;
        node nex;
        for(int i = 0;i < 8;i ++){
            nex.x = now.x + dx[i];
            nex.y = now.y + dy[i];
            if(vis[nex.x][nex.y]==0)
                nex.step = now.step+1,q.push(nex),ans[nex.step]++,vis[nex.x][nex.y]=1;
        }
    }
    for(int i = 0;i <= 20;i ++)
        cout<<ans[i]<<" ";//ans[i+1] += ans[i];
    cout<<endl;
}

int main()
{
    bfs();
    return 0;
}

这个表求得是每一步多增加的点数,可以得到以下数据

1 8 32 68 96 120 148 176 204 232 260 288 316 344 372 400 428 456 484 512 540

我们可以发现这张表从120开始后面每一次都是+28

从120开始这个序列就可以变成一个等差数列,但是题目是要我们求所有的,那就直接等差数列前n项和公式就好了,把第一项设为120或者120后面随意一个数字就好了,前n项求和后加上第一项前面的那些数的和就好了

这道题会爆long long ,我们用 unsigned long long 就好了

实现代码;

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
/*
struct node{
    int x,y,step;
};

int dx[] = {2,2,-2,-2,1,1,-1,-1};
int dy[] = {1,-1,1,-1,2,-2,2,-2};
int ans[10000],vis[1000][1000];
void bfs(){
    node now;
    queue<node>q;
    now.x = 500,now.y = 500,now.step = 0;
    ans[0] = 1;
    vis[500][500] = 1;
    q.push(now);
    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(now.step == 20) continue;
        node nex;
        for(int i = 0;i < 8;i ++){
            nex.x = now.x + dx[i];
            nex.y = now.y + dy[i];
            if(vis[nex.x][nex.y]==0)
                nex.step = now.step+1,q.push(nex),ans[nex.step]++,vis[nex.x][nex.y]=1;
        }
    }
    for(int i = 0;i <= 20;i ++)
        cout<<ans[i]<<" ";//ans[i+1] += ans[i];
    cout<<endl;
}

int main()
{
    bfs();
    return 0;
}
*/ 
//1 8 32 68 96 120 148 176 204 232 260 288 316 344 372 400 428 456 484 512 540
//1 9 41 109 205 325 473 649 853 1085 1345 1633 1949 2293 2665 3065 3493 3949 4433 4945 5485

int a[10] = {1, 9 ,41 ,109 ,205 ,325 ,473};
int main()
{
    ull t,n,cas = 1;
    ull ans;
    cin>>t;
    while(t--){
        cin>>n;
        if(n < 6) cout<<"Case #"<<cas++<<": "<<a[n]<<endl;
        else{
            ans = 148*(n-5) + (n-6)*(n-5)*14;
            cout<<"Case #"<<cas++<<": "<<ans+325<<endl;
        }
    }
    return 0;
}

 

hdu 6253 (bfs打表)

原文:https://www.cnblogs.com/kls123/p/9815661.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!