注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

百度之星 资格赛 1005 下棋  

2015-05-26 15:59:02|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1005


代码:(非AC代码)
#include <stdio.h>

int main()
{
int king_mov[8][2] = {
 {-1,1}, {0,1}, {1,1},
 {-1,0},        {1,0},
 {-1,-1},{0,-1},{1,-1}
};
int knight_mov[8][2] = {
 {-2,1},{-1,2},{1,2},{2,1},
 {-2,-1},{-1,-2},{1,-2},{2,-1}
};
int all_mov[64][2];
int count = 0;
for(int ik = 0; ik < 8 ; ++ik)
{
for(int in = 0; in < 8 ;++in)
{
all_mov[count][0] = king_mov[ik][0] + knight_mov[in][0];
all_mov[count][1] = king_mov[ik][1] + knight_mov[in][1];
count++;
}
}
for(int ic = 0; ic < count ; ++ic)
{
printf("%d %d\n",all_mov[ic][0],all_mov[ic][1]);
}
return 0;

AC代码
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <assert.h>
#define clr(a,b)    memset(a,b,sizeof(a))
using namespace std;

typedef long long LL;

int T;
int n, m, k;

int g[1010][1010];

int dx[8] = {-1,-2,-2,-1,1,2,2,1};
int dy[8] = {-2,-1,1,2,-2,-1,1,2};

int x,y,xx,yy;
queue<pair<int,int> > q;

int main()
{
//    freopen("in","r",stdin);

    scanf("%d",&T);
    int cas = 1;
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);

        scanf("%d%d",&x,&y);
        scanf("%d%d",&xx,&yy);

        int ans = max(abs(x-xx), abs(y-yy) );
        if(ans % 2 == 1)    ans++;

        printf("Case #%d:\n", cas++);

        clr(g, -1);
        while(!q.empty())    q.pop();

        g[xx][yy] = 0;
        q.push(make_pair(xx, yy));
        while(!q.empty())
        {
            pair<int,int> h = q.front();
            q.pop();
            int curx = h.first;
            int cury = h.second;

            if(g[curx][cury] > k)
                continue;

            for(int i=0; i<8; i++)
            {
                int nx = curx + dx[i];
                int ny = cury + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] != -1)
                    continue;

                g[nx][ny] = g[curx][cury] + 1;
//                printf("%d %d %d\n", nx, ny,  g[nx][ny]);
                q.push(make_pair(nx, ny));

                int t1 = g[nx][ny];
                int t2 = max(abs(nx - x), abs(ny - y));

                int t;

                if(t2 == 0)
                {
                    if(t1 == 0)    t = 2;
                    else if(t1 == 1)    t = 3;
                    else    t = t1;
                }
                else if(t1 >= t2)    t = t1;
                else
                {
                    if( (t2 - t1) % 2 == 0 ) t = t2;
                    else    t = t2 + 1;
                }
                ans = min(ans, t);
            }
        }

        if(ans > k)
            puts("OH,NO!");
        else
            printf("%d\n", ans);
    }

    return 0;
}
  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018