행렬찾기

1. 단순하게 자료구조 설정 2. sort 하는 것. 3. 힙, 퀵, 머지 찾아서 여러 번 반복하기 4. 링크드 리스트 더블 링크드 5. 이렇게만 이용하면 끝 6. 해쉬 포함

#include <stdio.h> #define swap(a, b, t) (t = a, a = b, b = t) typedef struct Mat { int row; int col; } mat; #define MAX 10 int board[MAX][MAX]; mat matrix[21]; int main() { freopen("input.txt", "r", stdin); int T, test_case; int N; int count; mat tmp; int i, j, k, l; setbuf(stdout, NULL); scanf("%d", &test_case); for (T = 1; T <= test_case; ++T) { count = 0; scanf("%d", &N); for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) scanf("%d", &board[i][j]); } for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { if (board[i][j] != 0) { matrix[count].row = matrix[count].col = 1; while ((j + (matrix[count].col) < N) && (board[i][j + (matrix[count].col)] != 0)) matrix[count].col++; // N 범위안에 들어오고, 숫자가 있을때까지 while while ((i + (matrix[count].row) < N) && (board[i + (matrix[count].row)][j] != 0)) matrix[count].row++; // N 범위안에 들어오고, 숫자가 있을떄까지 while for (k = 0; k < matrix[count].row; ++k) // 찾은거 0으로 만들고 { for (l = 0; l < matrix[count].col; ++l) board[i + k][j + l] = 0; } ++count; // count 하나 올림 } } } for (i = 0; i < count; ++i) // 이렇게 하면 일렬의 배열이 있을 떄, 검사를 진행 할 수 있군. sort 하는 방법 { for (j = 1; j < count - i; ++j) { if ((matrix[j - 1].row * matrix[j - 1].col > matrix[j].row * matrix[j].col) || ((matrix[j - 1].row * matrix[j - 1].col == matrix[j].row * matrix[j].col) && (matrix[j - 1].row > matrix[j].row))) { swap(matrix[j - 1], matrix[j], tmp); } } } printf("#%d %d ", T, count); for (i = 0; i < count; ++i) printf("%d %d ", matrix[i].row, matrix[i].col); printf("\n"); } return 0; }