AcWing 3223. 消除类游戏_暴力法
原题链接
简单
作者:
威子
,
2021-02-28 11:35:32
,
所有人可见
,
阅读 257
时间复杂度:
o(n^2)
取程序中的最多循环嵌套层数?这样算应该是O(n^2)的平方吧(****如果我说错了帮我改正留言哈****)
算法思路:
暴力枚举每一个位置,以改点为起点,上下为一组、左右为一组.分情况讨论
#include <bits/stdc++.h>
using namespace std;
const int N=35;
int a[N][N],s[N][N];
int row,col; //行、列
/*计算*/
void f(int x,int y,int val){
int up=x,down=x,left=y,right=y;
for(int i=x,j=y;i>=1;i--){ //循环上下个方向
if(a[i][j]==val) up--;
else break;
}
for(int i=x,j=y;i<=row;i++){
if(a[i][j]==val) down++;
else break;
}
for(int i=x,j=y;j>=1;j--){ //循环四个方向
if(a[i][j]==val) left--;
else break;
}
for(int i=x,j=y;j<=col;j++){ //循环四个方向
if(a[i][j]==val) right++;
else break;
}
//统计
if(down-up-1>=3){ //删除上下
for(int i=up+1,j=y;i<down;i++) s[i][j]=0;
}
if(right-left-1>=3){ //删除左右
for(int i=x,j=left+1;j<right;j++) s[i][j]=0;
}
}
int main(){
cin>>row>>col;
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
cin>>a[i][j];
s[i][j]=a[i][j];
}
}
//枚举每一个位置
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
f(i,j,a[i][j]);
}
}
//输出
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++)
cout<<s[i][j]<<" ";
cout<<endl;
}
return 0;
}