l_migrant 2021-09-28 16:44 采纳率: 83.3%
浏览 19
已结题

为什么 sx <= l && sy <= l只能对一半,而 sx < l && sy < l却可以ac?

我定义了一个305 * 305 的数组,所以就算等于l,pos[sx][sy]也没有越界。只是队列里多了一组数据而已,应该不会影响答案。为什么不可以等于l?
题目原题()
描述
背景
Somurolov先生精彩的象棋玩家的确,声称任何人但他可以从一个位置到另一个骑士这么快。你能打败他吗?
问题
你的任务是写一个程序来计算一个骑士达到从另一点所需要的最少步数,这样你才有机会要比Somurolov快。
对于不熟悉象棋的人来说,可能的骑士动作如图1所示.。
输入
输入开始与一个单一的行本身的情况下。
下一步跟踪N个场景。每个场景由三行包含整数。第一行指定棋盘边的长度L(4 < L = < 300)。整个板尺寸L×L的第二和第三行包含整数对{ 0,…,L-1 } * { 0,…,L-1 }指定开始和结束位置的骑士。整数由一个空格隔开。您可以假定这些位置是该方案的棋盘上的有效位置.。
输出
对于输入的每一个场景,你必须计算从起点到终点的最小的骑士移动量.。如果起点和终点相等,距离为零。距离必须写在一行。
样例输入
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
样例输出
5
28
0


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
void bfs(int, int);
const int maxn = 305;
int t, n, l, x0, y0, fx, fy, pos[maxn][maxn], que[maxn * maxn][3];
int dx[8] = {2, 2, 1, -1, -2, -2, -1, 1};
int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    while(t < n)
    {
        t++;
        cin >> l >> x0 >> y0 >> fx >> fy;
        memset(pos, -1, sizeof(pos));    memset(que, 0, sizeof(que));
        bfs(x0, y0);
        cout << pos[fx][fy] << endl;
    }
    return 0;
}
void bfs(int x, int y)
{
    int head = 1, tail = 1;
    que[1][0] = x;    que[1][1] = y;    que[1][2] = 0;    pos[x][y] = 0;
    while(head <= tail)
    {
        for(int i = 0; i < 8; i++)
        {
            int sx = que[head][0] + dx[i], sy = que[head][1] + dy[i];
            if(sx >= 0 && sy >=0 && sx < l && sy < l && pos[sx][sy] == -1)
            {
                pos[sx][sy] = que[head][2] + 1;
                tail++;
                que[tail][0] = sx;    que[tail][1] = sy;    que[tail][2] = pos[sx][sy];
                if(pos[fx][fy] >= 0)
                {
                    head = tail;
                    //cout << pos[fx][fy] << endl;
                    break;
                }
            }
        }
        head++;
    }
}
  • 写回答

1条回答 默认 最新

  • qfl_sdu 2021-09-28 16:52
    关注

    if语句中,sx和sy会对que的值产生影响,而que又会对pos的值产生影响,所以<=多出来的等号会对你的结果有影响。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月6日
  • 已采纳回答 9月28日
  • 创建了问题 9月28日

悬赏问题

  • ¥30 这是哪个作者做的宝宝起名网站
  • ¥60 版本过低apk如何修改可以兼容新的安卓系统
  • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
  • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
  • ¥50 有数据,怎么用matlab求全要素生产率
  • ¥15 TI的insta-spin例程
  • ¥15 完成下列问题完成下列问题
  • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
  • ¥15 YoloV5 第三方库的版本对照问题
  • ¥15 请完成下列相关问题!