在 N*N 的棋盘中,M 个象不能走多少格?
How many squares can M bishops cannot go in an N*N chess board?
我目前正在开发一个程序,该程序计算 M 数量的象在 N*N 大小的国际象棋网格上的移动。我有一个程序只能为一个主教找到无法访问的方块。有人可以帮我解决这个问题吗?
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int ways(int r,int c,int n)
{
int TL,TR,BL,BR;
TL = min(r,c) - 1;
TR = min(r,(n+1)-c) - 1;
BL = n - max(r,(n+1)-c);
BR = n - max(r,c);
return (TL+TR+BL+BR);
}
int main()
{
int r,c,n;
cin >> r >> c >> n;
cout << n*n - ways(r,c,n);
return 0;
}
如果象的行和列都是4,网格大小是8*8,那么象有51个方格不能访问。但我不知道该如何处理。
有几种方法可以完成这个任务,但我会给你一个简单的算法。
这些主教不能访问的方格数=
总个方格数-那些主教可以访问的方格数
既然计算方格总数(n * n)很容易,问题就归结为计算这些主教可以访问的方格总数他们给定的位置。
在您的代码中,您没有读取主教的数量及其初始坐标。这应该是第一步。
由于您使用的是 C++,因此可以使用 std::set
of std::pair
来简化您的任务。集合用于存储唯一元素,因此您可以使用它来存储主教可以访问的位置并避免重复。一对可用于将位置存储为坐标 (i, j).
遍历每个主教并计算他们可以访问的方格并将其添加到集合中。最后,您将主教可以覆盖的方格总数作为该组的大小。
然后使用上面的公式得到你想要的结果。
下面是该方法的一个实现:
#include <iostream>
#include <set>
#include <utility>
using namespace std;
int main()
{
int n; // Size of the chess board
int m; // Number of bishops
int x, y; // Initial location of a bishop
int i, j; // Coordinates for iteration
// Read the limits
cin >> n >> m;
if (n < 0) n = 0;
// Read the location of the bishops
set<pair<int, int>> bishops;
for (i = 0; i < m; ++i)
{
cin >> x >> y;
if (x >= 0 && x < n && y >= 0 && y < n)
bishops.insert({x, y});
}
// This is the key
set<pair<int, int>> visitableLocations;
// Calculate the squares that could be visited by all the bishops
for (const auto& bishop : bishops)
{
x = bishop.first;
y = bishop.second;
/*
You don't need this after the edit made to your post
Because you don't consider its initial square as visitable
// Add the original location of the bishop
if (x >= 0 && x < n && y >= 0 && y < n)
visitableLocations.insert({x, y});
*/
// Check all the diagonal directions
// Within the boundaries of the board
// No other bishop should block the way
// auto debug = [&](){cout << i << ' ' << j << '\n';};
// north-east
i = x; j = y;
while (++i < n && ++j < n)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// north-west
i = x; j = y;
while (--i >= 0 && ++j < n)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// south-east
i = x; j = y;
while (++i < n && --j >= 0)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// south-west
i = x; j = y;
while (--i >= 0 && --j >=0)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
}
// Now get the final answer
int ans = (n * n) - visitableLocations.size();
cout << ans;
return 0;
}
我目前正在开发一个程序,该程序计算 M 数量的象在 N*N 大小的国际象棋网格上的移动。我有一个程序只能为一个主教找到无法访问的方块。有人可以帮我解决这个问题吗?
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int ways(int r,int c,int n)
{
int TL,TR,BL,BR;
TL = min(r,c) - 1;
TR = min(r,(n+1)-c) - 1;
BL = n - max(r,(n+1)-c);
BR = n - max(r,c);
return (TL+TR+BL+BR);
}
int main()
{
int r,c,n;
cin >> r >> c >> n;
cout << n*n - ways(r,c,n);
return 0;
}
如果象的行和列都是4,网格大小是8*8,那么象有51个方格不能访问。但我不知道该如何处理。
有几种方法可以完成这个任务,但我会给你一个简单的算法。
这些主教不能访问的方格数=
总个方格数-那些主教可以访问的方格数
既然计算方格总数(n * n)很容易,问题就归结为计算这些主教可以访问的方格总数他们给定的位置。
在您的代码中,您没有读取主教的数量及其初始坐标。这应该是第一步。
由于您使用的是 C++,因此可以使用 std::set
of std::pair
来简化您的任务。集合用于存储唯一元素,因此您可以使用它来存储主教可以访问的位置并避免重复。一对可用于将位置存储为坐标 (i, j).
遍历每个主教并计算他们可以访问的方格并将其添加到集合中。最后,您将主教可以覆盖的方格总数作为该组的大小。
然后使用上面的公式得到你想要的结果。
下面是该方法的一个实现:
#include <iostream>
#include <set>
#include <utility>
using namespace std;
int main()
{
int n; // Size of the chess board
int m; // Number of bishops
int x, y; // Initial location of a bishop
int i, j; // Coordinates for iteration
// Read the limits
cin >> n >> m;
if (n < 0) n = 0;
// Read the location of the bishops
set<pair<int, int>> bishops;
for (i = 0; i < m; ++i)
{
cin >> x >> y;
if (x >= 0 && x < n && y >= 0 && y < n)
bishops.insert({x, y});
}
// This is the key
set<pair<int, int>> visitableLocations;
// Calculate the squares that could be visited by all the bishops
for (const auto& bishop : bishops)
{
x = bishop.first;
y = bishop.second;
/*
You don't need this after the edit made to your post
Because you don't consider its initial square as visitable
// Add the original location of the bishop
if (x >= 0 && x < n && y >= 0 && y < n)
visitableLocations.insert({x, y});
*/
// Check all the diagonal directions
// Within the boundaries of the board
// No other bishop should block the way
// auto debug = [&](){cout << i << ' ' << j << '\n';};
// north-east
i = x; j = y;
while (++i < n && ++j < n)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// north-west
i = x; j = y;
while (--i >= 0 && ++j < n)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// south-east
i = x; j = y;
while (++i < n && --j >= 0)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
// south-west
i = x; j = y;
while (--i >= 0 && --j >=0)
if (bishops.find({i, j}) == bishops.end())
visitableLocations.insert({i, j});//debug();}
}
// Now get the final answer
int ans = (n * n) - visitableLocations.size();
cout << ans;
return 0;
}