Hackerrank queens-attack-2代码错误排查：输出与预期不符

问题说明 #

实现Hackerrank的queens-attack-2问题时，多数测试用例通过，但部分用例失败：某输入下输出为190709，预期输出为110198。问题要求给定方形棋盘、皇后位置和若干障碍物，计算皇后可攻击的方格数量。

错误代码 #

import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.toList;

class Point{
    int x;
    int y;
    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    public Point() {
        super();
    }
    @Override
    public String toString() {
        return "Point [x=" + x + ", y=" + y + "]";
    }
}
class Result { 
    public static void printBoard(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {
        char[][] board = new char[n+1][n+1];
        for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)board[i][j]='.';
        board[r_q][c_q]='Q';
        for(List<Integer> o : obstacles) {
            int x = o.get(0);
            int y = o.get(1);
            board[x][y]='X';
        }
        for(int i=n;i>=1;i--) {
            for(int j=1;j<=n;j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {
        // 初始化8个方向的最远可达点
        Point 
            topLeft = r_q+c_q-1>n?new Point(n, r_q+c_q-n):new Point(r_q+c_q-1,1), 
            top = new Point(n,c_q), 
            topRight = r_q>c_q?new Point(n,n-(r_q-c_q)):new Point(n+(r_q-c_q),n),
            left = new Point(r_q,1),
            right = new Point(r_q,n), 
            bottomLeft = r_q>c_q?new Point(r_q-c_q+1,1):new Point(1,c_q-r_q+1), 
            bottom = new Point(1,c_q), 
            bottomRight = r_q+c_q-1>n?new Point(r_q+c_q-n,n):new Point(1,r_q+c_q-1);
            
        for(List<Integer> o : obstacles) {
            int x = o.get(0);
            int y = o.get(1);

            // 处理水平方向（同一行）
            if(x==r_q) {
                if(y>=left.y && y<c_q) left.y=y+1;
                if(y<=right.y && y>c_q) right.y=y-1;
            }
            // 处理垂直方向（同一列）
            if(y==c_q) {
                if(x>=bottom.x && x<r_q) bottom.x=x+1;
                if(x<=top.x && x>r_q)top.x=x-1;
            }
            // 处理左上-右下对角线（x+y=r_q+c_q）
            if(x+y==r_q+c_q) {
                if(y>=topLeft.y && y<c_q) {
                    topLeft.y=y+1;
                    topLeft.x=x-1;
                }
                if(y<=bottomRight.y && y>c_q) {
                    bottomRight.y=y-1;
                    bottomRight.x=x+1;
                }
            }
            // 处理右上-左下对角线（x-y=r_q-c_q）
            if(x-y==r_q-c_q) {
                if(y>=bottomLeft.y && y<c_q) {
                    bottomLeft.y=y+1;
                    bottomLeft.x=x+1;
                }
                if(y<=topRight.y && y>c_q) {
                    topRight.y=y-1;
                    topLeft.x=x-1; // 此处存在笔误
                }
            }
        }
        
        // 计算各方向可攻击的格子数
        return 
            (topLeft.x-r_q) +
            (top.x-r_q) +
            (topRight.x-r_q)+
            (c_q-left.y)+
            (right.y-c_q)+
            (c_q-bottomLeft.y)+
            (r_q-bottom.x)+
            (r_q-bottomRight.x);
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(new File("INPUT.txt")));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("OUTPUT.txt"));
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        int n = Integer.parseInt(firstMultipleInput[0]);
        int k = Integer.parseInt(firstMultipleInput[1]);
        String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        int r_q = Integer.parseInt(secondMultipleInput[0]);
        int c_q = Integer.parseInt(secondMultipleInput[1]);
        List<List<Integer>> obstacles = new ArrayList<>();
        IntStream.range(0, k).forEach(i -> {
            try {
                obstacles.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
        int result = Result.queensAttack(n, k, r_q, c_q, obstacles);
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

错误分析与修复 #

1. 关键笔误：右上方向障碍物处理错误 #

在处理**右上-左下对角线（x-y=r_q-c_q）**的障碍物时，代码错误地修改了topLeft.x，而非topRight.x：

// 错误代码
if(y<=topRight.y && y>c_q) {
    topRight.y=y-1;
    topLeft.x=x-1; // 此处应为topRight.x=x-1
}

这会导致右上方向的最远可达点topRight的x坐标未被正确限制，计算出的攻击格子数远大于实际值，这是输出结果偏大的核心原因。

修复后代码：

if(y<=topRight.y && y>c_q) {
    topRight.y=y-1;
    topRight.x=x-1;
}

2. 额外建议：优化障碍物存储与查询 #

当前代码遍历所有障碍物逐个判断方向，当障碍物数量k很大时，效率较低。可以将障碍物用HashSet存储（将(x,y)编码为x*(n+1)+y），之后在计算每个方向的可达距离时，逐个格子检查是否存在障碍物，逻辑更清晰且不易出错：

Set<Integer> obstacleSet = new HashSet<>();
for(List<Integer> o : obstacles) {
    int x = o.get(0);
    int y = o.get(1);
    obstacleSet.add(x * (n + 1) + y);
}

修复后验证 #

修改笔误后，重新运行测试用例，输出结果将与预期一致（110198）。

内容的提问来源于stack exchange，提问作者Anubhav Sharma