思路:将二维坐标转化为一维坐标 然后用map存储离散的森林数据坐标
坐标是从0,0开始
则转化为一维坐标为: `x*m+y` n是列数(注意:这里的列数,不是数组里面的边界列数,而是实际列数)
则反过来转化为二维坐标
x = n / m
y = n % m 这里的n为转化后的一维坐标
坐标是从1,1开始的
则转化为 (x - 1)*n + y
则反过来转化为二维坐标
x = n / m + 1
y = (n - 1)%m + 1 这里的n为转化后的一维坐标
tle代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N];
PII node[N];
map<LL,int> st;
int n,S;
int l;
LL get(int x,int y){
return (LL)x*(l+1)+y;
}
bool check(int idx)
{
int x = node[idx].first,y = node[idx].second;
for(int i = 0;i <= S;i++){
for(int j = 0;j <= S;j++){
int tx = x + i,ty = y + j;
if(tx > l || ty > l) return false;
if(st.count(get(tx,ty)) != a[i][j]) return false;
}
}
return true;
}
int main()
{
cin>>n>>l>>S;
for(int i = 0;i < n;i++){
int x,y;
cin>>x>>y;
node[i].first = x;
node[i].second = y;
st[get(x,y)] = true;
// cout << get(x,y)<<endl;
}
for(int i = S;i >= 0;i--){
for(int j = 0;j <= S;j++){
cin>>a[i][j];
}
}
int res = 0;
for(int i = 0;i < n;i++){
if(check(i)){
res++;
}
}
cout<<res;
return 0;
}
写unordered_map AC
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N];
PII node[N];
unordered_map<LL,int> st;
int n,S;
LL m;
bool check(int idx)
{
int x = node[idx].first,y = node[idx].second;
for(int i = 0;i <= S;i++){
for(int j = 0;j <= S;j++){
int c = x + i,d = y + j;
if(c > m || d > m || st.count((LL)c*(m+1)+d) != a[i][j]) return false;
// cout<<"---"<<c<<" "<<d<<endl;
// cout<<i<<" "<<j<<endl;
}
}
return true;
}
int main()
{
cin>>n>>m>>S;
for(int i = 0;i < n;i++){
int x,y;
cin>>x>>y;
node[i].first = x;
node[i].second = y;
st[(LL)x*(m+1)+y] = true;
}
for(int i = S;i >= 0;i--){
for(int j = 0;j <= S;j++){
cin>>a[i][j];
}
}
int res = 0;
for(int i = 0;i < n;i++){
if(check(i)){
res++;
}
}
cout<<res;
return 0;
}