Untitled
unknown
plain_text
a year ago
3.4 kB
8
Indexable
#include<iostream> using namespace std; int T,N,a[101][101],visited[101][101]; int visited2[101][101]={0}; int res; int used[101][101]={0}; int used2[101][101]={0}; int dr[4]={0,-1,0,1}; int dc[4]={-1,0,1,0}; int map[101][101]; const int MAX=200000; struct Queue { int queue[MAX]; int front; int rear; Queue(){ reset(); } void reset(){ front=-1; rear=-1; } void push(int value){ queue[++rear]=value; } int pop(){ return queue[++front]; } bool isEmpty(){ return front==rear; } }; void bfs(int x,int y){ Queue q; q.push(x); q.push(y); visited2[x][y]=1; int value=a[x][y]; while(!q.isEmpty()){ int r=q.pop(); int c=q.pop(); for (int i =0 ;i<4;i++){ int _r=r+dr[i]; int _c=c+dc[i]; if(_r>=0&&_c>=0&&_r<N&&_c<N && a[_r][_c]==value&&!visited2[_r][_c]){ visited2[_r][_c]=1; q.push(_r); q.push(_c); } } } } void duyet0(int x,int y){ for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ visited[i][j]=0; used[i][j]=0; used2[i][j]=0; visited2[i][j]=0; } } Queue q; q.push(x); q.push(y); visited[x][y]=6; while(!q.isEmpty()){ int r=q.pop(); int c=q.pop(); for (int i =0 ;i<4;i++){ int _r=r+dr[i]; int _c=c+dc[i]; if(_r>=0&&_c>=0&&_r<N&&_c<N && a[_r][_c]==0&&!visited[_r][_c]){ visited[_r][_c]=6; q.push(_r); q.push(_c); } } } int counting[101][101]={0}; int count[101]={0}; for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ if(visited[i][j]==6){ for (int k=0 ;k<4;k++){ int r=i+dr[k]; int c=j+dc[k]; if(r>=0&&c>=0&&r<N&&c<N&& !used[r][c]&&a[r][c]!=0){ int value=a[r][c]; counting[r][c]=value; count[value]+=1; used[r][c]=1; } } } } } for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ if(counting[i][j]>0){ int value=counting[i][j]; /*used2[i][j]=1; count[value]++;*/ for (int k=0 ;k<4;k++){ int r=i+dr[k]; int c=j+dc[k]; if(r>=0&&c>=0&&r<N&&c<N&& !used2[r][c]&&a[r][c]==value){ used2[r][c]=1; count[value]++; } } } } } int max=0; int value=0; for (int i=1 ;i<=5;i++){ if(count[i]>=max){ max=count[i]; value=i; } } for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ if(visited[i][j]==6){ map[i][j]=value; } } } } void merge(){ for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ if(map[i][j]>0){ int value=map[i][j]; a[i][j]=value; } } } } void reset(){ for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ visited[i][j]=0; used[i][j]=0; used2[i][j]=0; visited2[i][j]=0; map[i][j]=0; } } } int main(){ freopen("input.txt","r",stdin); cin>>T; for (int t=1; t<=T;t++){ cin>>N; reset(); for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ cin>>a[i][j]; } } for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ //reset(); if(a[i][j]==0&&!visited[i][j]){ duyet0(i,j); } } } merge(); res=0; for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ visited2[i][j]=0; } } for (int i=0 ;i<N;i++){ for (int j=0 ;j<N;j++){ if(!visited2[i][j]){ bfs(i,j); res++; } } } cout<<"Case #"<<t<<endl; cout<<res<<endl; } return 0; }
Editor is loading...
Leave a Comment