B题,题目描述如下:
点击“提示”查看下文!!!
提示1:怎样才是一个合法的子矩阵?
题目要求每个区域内的两个数的和都是奇数;我们不难发现一个性质:奇数+奇数=偶数,偶数+奇数=奇数。那么我们可以对数组做一个预处理。为了方便大家直观的感受,也是我赛时的小技巧,我把数组模拟出来:
我们仅需要组成一对 “ [ * . ] ”即为一对合法的子矩阵
提示2:怎样存放我们的合法子矩阵?
不妨开一个 vector<pair<int,int>> key; 来存放这个合法的子矩阵。
对于为什么用PII的方式呢 ? 因为存放的是两个点。
对于某个点来说,你将其以以下方式存点即可:
key = x*6 + y
对于一个 合法的子矩阵 其中有两个点,所以我们不妨采用 PII 的方式存放每个点的Key值{ Node1 , Node2 }
提示3:那怎么判断区域重叠呢?
Ciallo~(∠・ω< )⌒★聪明的你肯定想到了,只要两张牌任意一点相同了就是区域覆盖了,只要写个check()函数对其判断下就好啦.
剩下的就交给三层for循环暴力枚举了吧,加上判断即可。
using namespace std;
using ll=long long;
using PLL=pair<ll,ll>;
#define int long long
const int INF=1e8;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vector<PLL> key;
//判断是否区域覆盖
bool check(int ka,int kb){
auto [p1,p2]=key[ka];
auto [q1,q2]=key[kb];
//存放的都是点的key值,只要任意两个key值有碰撞那就是相同的点
return(p1==q1||p1==q2||p2==q1||p2==q2);
}
void solve(){
int n=6;
queue<PLL> q;
vector<vector<char>> mp(n+1,vector<char>(n+1));
//预处理下数组,然后可视化看看
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
//奇数,加入队列,只做一次bfs
if(x&1){
mp[i][j]='*';
q.push({i,j});
}else{
mp[i][j]='.';
}
}
}
//打印出数组
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<mp[i][j]<<" ";
// }
// cout<<endl;
// }
//对所有的“ * ”进行扫描,匹配【* .】
//并将两点信息加入key数组中
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx<1||ny<1||nx>n||ny>n||mp[nx][ny]=='*')continue;
//对应两点的“key值”
ll k1=x*6+y;
ll k2=nx*6+ny;
key.emplace_back(k1,k2);
}
}
// cout<<key.size()<<endl;
int m=key.size();
//暴力枚举三层for循环
int ans=0;
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
if(check(i,j))continue;
for(int k=j+1;k<m;k++){
if(check(j,k)||check(i,k))continue;
ans++;
}
}
}
cout<<ans<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
希望对各位有帮助
真的喜欢⌬gg的比赛,感谢!!!Respect!!!

京公网安备 11010502036488号