| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
绝地游戏外挂辅助教学千里之行 始于足下
共有 462 人关注过本帖
标题:[USACO3.3]亚瑟王的宫殿 Camelot 有点bug,求大神。调试3天了┭┮﹏┭┮
只看楼主 收藏
罗进瑶
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2017-8-9
结帖率:0
  已结贴   问题点数:20  回复次数:7   
[USACO3.3]亚瑟王的宫殿 Camelot 有点bug,求大神。调试3天了┭┮﹏┭┮
https://www.luogu.org/problem/show?pid=1930


> Run 13: Execution error: Your program did not produce an answer
        that was judged as correct. The program stopped at 0.028 seconds;
        it used 7132 KB of memory. At character number 2, your answer says
        '0' while the correct answer says '1'.

        Here are the respective outputs:
        ----- our output ---------
        11
        ---- your output ---------
        10
        --------------------------

        ------ Data for Run 13 [length=24 bytes] ------
        8 8
        D 5
        A 3 A 8 H 1 H 8
        ----------------------------

程序代码:
/*
ID:luojiny1
LANG:C++
TASK:camelot
*/
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int maxR=31,maxC=28;
int R,C,n=0;
int kx,ky,nx[maxR*maxC],ny[maxR*maxC],d[maxC][maxR][maxC][maxR],ans=INF;

struct point{
    int x,y,step;
};
void bfs(int sx,int sy){
    int dx[8]={-1,1,2,2,1,-1,-2,-2};
    int dy[8]={2,2,1,-1,-2,-2,-1,1};
    bool vis[maxC][maxR]={0};
    queue<point>Q;
    Q.push((point){sx,sy,0});
    while(!Q.empty()){
        point a=Q.front();Q.pop();
        int x=a.x,y=a.y;
        if(vis[x][y])continue;
        vis[x][y]=1;
        d[sx][sy][x][y]=a.step;
        for(int i=0;i<8;i++){
            int newx=x+dx[i],newy=y+dy[i];
            if(newx>=0&&newx<C&&newy>=0&&newy<R)Q.push((point){newx,newy,a.step+1});
        }
    }
   
}
int main()
{
//    freopen("camelot.in","r",stdin);
//    freopen("camelot.out","w",stdout);
    memset(d,0x3f3f3f3f,sizeof(d));
    char ch;
    scanf("%d %d\n",&R,&C);
    scanf("%c %d\n",&ch,&ky);
    kx=ch-'A',ky--;
    while((ch=getchar())!=EOF)if(ch>='A'&&ch<='Z'){
        scanf("%d",&ny[n]);
        ny[n]--,nx[n++]=ch-'A';
        bfs(nx[n-1],ny[n-1]);
    }
    if(n==0){
        printf("0\n");
        return 0;
    }
    for(int dx=-1;dx<=1;dx++)
    for(int dy=-1;dy<=1;dy++){
        int newn=dx+kx,newm=dy+ky;
        if(newn>=0&&newn<C&&newm>=0&&newm<R)bfs(newn,newm);}
        
    for(int newx=0;newx<C;newx++)
    for(int newy=0;newy<R;newy++)
    {
        int t=0;
        for(int i=0;i<n;i++)
            t+=d[nx[i]][ny[i]][newx][newy];
        for(int dx=-1;dx<=1;dx++)
        for(int dy=-1;dy<=1;dy++){
            int newn=dx+kx,newm=dy+ky;
            if(newn>=0&&newn<C&&newm>=0&&newm<R)
            for(int i=0;i<n;i++)   
            ans=min(ans,t-d[nx[i]][ny[i]][newx][newy]+d[nx[i]][ny[i]][newn][newm]+abs(kx-newn)+abs(ky-newm)+min(d[newn][newm][newx][newy],abs(newn-newx)+abs(newm-newy)));
        }
    }
    printf("%d\n",ans);
    return 0;
}


[此贴子已经被作者于2017-8-9 12:54编辑过]

2017-08-09 12:53
罗进瑶
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2017-8-9
  得分:0 
@xzlxzlxzl
@renkejun1942
@ehszt
@jklqwe111
2017-08-09 12:55
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:24
帖 子:1582
专家分:5131
注 册:2016-12-1
  得分:7 
这些题我不熟,但是给你个链接,或许能帮到你。
http://blog.csdn.net/csyzcyj/article/details/9970205

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-08-09 16:57
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:25
帖 子:3983
专家分:11326
注 册:2016-10-22
  得分:7 
以下是引用罗进瑶在2017-8-9 12:55:46的发言:

@xzlxzlxzl
@renkejun1942
@ehszt
@jklqwe111

终于把九九排除了~很开心啊~因为最近知道自己其实不咋的~终于不用再顶大神的称号了哈~~~

[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-08-09 20:14
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:25
帖 子:3983
专家分:11326
注 册:2016-10-22
  得分:0 
啊~看了代码原来就是用的是bfs~具体我可以参考一下~这次我就当回学生看看能不能学到些东西哈~

PS:不过在3楼提供的链接看到用dfs剪枝也是可以的~

看懂大概思路了~大概就是用一个四元数组保存骑士任意两点间的最短距离。然后再求出所有骑士到该点的距离和最后再考虑国王的行动情况~

[此贴子已经被作者于2017-8-9 20:52编辑过]


[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-08-09 20:25
静水且流深
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:7
帖 子:29
专家分:133
注 册:2017-7-7
  得分:7 
回复 5楼 九转星河
久久很不服气呀
2017-08-09 20:49
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:25
帖 子:3983
专家分:11326
注 册:2016-10-22
  得分:0 
回复 6楼 静水且流深
以下是引用静水且流深在2017-8-9 20:49:37的发言:

久久很不服气呀


没有啊~我真的感觉自己不咋的~特别是对于一些真正有实力的高手来说~所以我愿意当一名学生~~

更何况~最近我都没咋编程了~

[此贴子已经被作者于2017-8-9 20:54编辑过]


[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-08-09 20:53
静水且流深
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:7
帖 子:29
专家分:133
注 册:2017-7-7
  得分:0 
回复 7楼 九转星河
言不由衷,没事,大神还是很厉害的!
2017-08-11 00:05







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.199221 second(s), 8 queries.
Copyright©2004-2017, BCCN.NET, All Rights Reserved