Untitled
plain_text
2 months ago
2.1 kB
2
Indexable
Never
#include <iostream> using namespace std; int st[1000]; int top; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; void push(int x){ top++; st[top] = x; } int pop(){ int x = st[top]; top--; return x; } int main(){ freopen("input.txt","r",stdin); int x,T; cin>>T; for (x = 0; x < T; x++){ int N,dem=0,max=0; cin>>N; int A[25][25],i,j; for (i = 0; i < N; i++) for (j = 0; j < N; j++) cin>>A[i][j]; for (i = 0; i < N; i++) for (j = 0; j < N; j++){ if (A[i][j] ==1){ int d = 0; dem++; top = -1; push(i); push(j); A[i][j] = 0; d++; while (top>= 1){ int col = pop(); int row = pop(); for (int k = 0; k <4; ++k){ int x1 = row + dx[k]; int y1 = col + dy[k]; if (x1>=0 && x1<N && y1>=0 && y1<N && A[x1][y1] == 1){ push(x1); push(y1); A[x1][y1] = 0; d++; } } } if (max < d) max = d; } } cout<<dem<<" "<<max << endl; } return 0; } /* 5 5 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 9 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 17 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 7 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 5 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 */