/*
* Problem :: 16924 / 십자가 찾기
*
* Kind :: Simulation
*
* Insight
* - 십자가로 주어진 모양을 만들 수 있는가?
* + 만들 수 있는지 없는지만 판별하면 된다
* # 만들 수 있는 경우, 십자가의 최소 개수를 구하지 않아도 된다
* -> 그냥 십자가 놓을 수 있으면 다 놓아보고 판단하면 되지 않을려나?
*
* - 시간 복잡도를 정확히 계산하기가 꽤나 복잡하다
* + 각 점을 기준으로 십자가를 놓을 때 최대 s 의 범위가 달라진다
* # 근데 max(N,M)=100 이라서 O(N^4) 까지 괜찮은데
* 이정도면 다 놓아봐도 괜찮을 것 같다 => 실제로 괜찮았다
*
* Point
* - 주어진 모양을 만들 수 있는 최소 십자가의 개수를 구하는 것이 아니다
* 그냥 모양만 만들면 된다
* + 실제로 모양이 만들어졌는지 확인하기 위한 배열이 필요하다
*
* - 문제는 왼쪽 맨 윗칸을 (1,1) 로 설정했지만
* 코드에서는 편의상 (0,0) 으로 보았다
* + 십자가 정보 넣을 때 (+1,+1) 만 해주면 문제푸는데 아무상관 없다
*
* - 십자가 개수가 N*M 개 이하여야 하는데
* 어차피 십자가 최소크기가 1 이고 기본적으로 5칸을 차지해서
* 절대 십자가 개수가 N*M 개 되는 일은 없다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, M;
char board[100][100];
bool isChecked[100][100];
struct Cross { int x, y, s; };
int dx[4] = {+1, 0, 0, -1};
int dy[4] = {0, +1, -1, 0};
#define INF 987654321
// Set up : Functions Declaration
bool isValid(int x, int y);
int getMaxS(int x, int y);
void putCross(int x, int y, int s);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> board[i][j];
}
}
// Process
int k = 0; /* 십자가의 개수 */
vector<Cross> crosses; /* 십자가이 정보가 담긴 Vector */
for (int x=1; x<N-1; x++) { /* 문제에서는 시작칸이 (1,1)
* 코드에서는 시작칸이 (0,0) */
for (int y=1; y<M-1; y++) { /* (0~(N-1), 0) 과 (0, 0~(M-1) 에는
* 십자가를 놓을 수 없음
* 그래서 (1~(N-2), 1~(M-2)) 칸만 탐색 */
if (board[x][y] == '*') { /* 현재칸이 별표면 */
int s = getMaxS(x, y); /* 이 칸을 중심으로
* 십자가를 놓을 때 최대 크기를 구함 */
if (s >= 1) { /* 최대 크기가 1 이상이면 */
putCross(x, y, s); /* 십자가를 놓음 */
k++; /* 십자가 개수 갱신 */
crosses.push_back({x+1, y+1, s}); /* 십자가 정보 저장 */
}
}
}
}
// Control : Output
bool isPossible = true; /* 주어진 모양을 만들 수 있는지 여부 */
for (int x=0; x<N; x++) {
if (not(isPossible)) break;
for (int y=0; y<M; y++) {
/* 별표인 칸인데 체크안된 칸이 있으면 */
if (board[x][y] == '*' && not(isChecked[x][y])) {
isPossible = false; /* 모양 만들기 불가능 */
break;
}
}
}
if (not(isPossible))
cout << -1 << endl;
else {
cout << k << endl;
for (Cross c : crosses) {
cout << c.x << ' ' << c.y << ' ' << c.s << endl;
}
}
}
// Helper Functions
bool isValid(int x, int y)
/* 주어진 좌표가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
return x >= 0 && x < N && y >= 0 && y < M;
}
int getMaxS(int x, int y)
/* 주어진 좌표에서 놓을 수 있는 십자가의 최대 크기를 구함 */
{
int maxS = INF;
for (int i=0; i<4; i++) { /* 아래쪽, 오른쪽, 왼쪽, 위쪽 차례로 검사
* 각 방향으로 놓아진 별표의 개수의 최솟값이
* 십자가의 최대 크기 */
int s = 0; /* (x,y) 에서 (dx[i], dy[i]) 방향으로 놓아진 별표의 개수 */
int ax = x + dx[i];
int ay = y + dy[i];
while (isValid(ax, ay) && board[ax][ay] == '*') {
s++;
ax += dx[i];
ay += dy[i];
}
maxS = min(maxS, s); /* 십자가의 최대 크기 갱신 */
}
return maxS;
}
void putCross(int x, int y, int s)
/* (x,y) 에 크기 s 인 십자가를 놓음 */
{
isChecked[x][y] = true;
for (int i=1; i<=s; i++) {
isChecked[x+i][y] = true;
isChecked[x-i][y] = true;
isChecked[x][y+i] = true;
isChecked[x][y-i] = true;
}
}