南阳河南网站建设价格,wordpress获取tags,网站建设小组,网站开发后端是什么目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
在一个 8x…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 描述
在一个 8x8 的棋盘上放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组 queens 表示黑皇后的位置以及一对坐标 king 表示白国王的位置返回所有可以攻击国王的皇后的坐标(任意顺序)。 示例 1 输入queens [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king [0,0]
输出[[0,1],[1,0],[3,3]]
解释
[0,1] 的皇后可以攻击到国王因为他们在同一行上。
[1,0] 的皇后可以攻击到国王因为他们在同一列上。
[3,3] 的皇后可以攻击到国王因为他们在同一条对角线上。
[0,4] 的皇后无法攻击到国王因为她被位于 [0,1] 的皇后挡住了。
[4,0] 的皇后无法攻击到国王因为她被位于 [1,0] 的皇后挡住了。
[2,4] 的皇后无法攻击到国王因为她和国王不在同一行/列/对角线上。示例 2 输入queens [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king [3,3]
输出[[2,2],[3,4],[4,4]]示例 3 输入queens [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king [3,4]
输出[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]提示
1 queens.length 63queens[i].length 20 queens[i][j] 8king.length 20 king[0], king[1] 8一个棋盘格上最多只能放置一枚棋子。 解题思路
* 解题思路
* 从king出发使用searchForward方法分别向8个方向分别尝试。如果有满足条件的则返回。如果没有满足的则返回空数组。
代码
class Solution1222
{
public:vectorvectorint fowards {{1, 0}, {1, 1}, {1, -1}, {0, 1}, {0, -1}, {-1, 0}, {-1, 1}, {-1, -1}};vectorint searchForward(setstring queenSet, vectorint king, vectorint forward){while (king[0] 0 king[1] 0 king[0] 8 king[1] 8){king[0] king[0] forward[0];king[1] king[1] forward[1];if (queenSet.find(to_string(king[0]) _ to_string(king[1])) ! queenSet.end()){return vectorint{king[0], king[1]};}}return vectorint{};}vectorvectorint queensAttacktheKing(vectorvectorint queens, vectorint king){setstring queenSet;for (int i 0; i queens.size(); i){queenSet.insert(to_string(queens[i][0]) _ to_string(queens[i][1]));}vectorvectorint list;for (int i 0; i fowards.size(); i){vectorint result searchForward(queenSet, king, fowards[i]);if (result.size() 0){list.push_back(result);}}return list;}
};
