// https://prologin.org/train/2015/semifinal/manoir_en_relief #include #include #include using namespace std; vector> solution; // Parcours récursif "Depth First Search" int dfs(const vector> &mat, vector> &vis, const int m, const int n, const int i, const int j) { if(vis[i][j]) return 0; int ans = 1; vis[i][j] = true; int path = 0; int up = 0, left = 0, down = 0, right = 0; if(i < m - 1 && mat[i + 1][j] == mat[i][j]) // bas { down = dfs(mat, vis, m, n, i + 1, j); path += down; } if(j < n - 1 && mat[i][j + 1] == mat[i][j]) // droite { right = dfs(mat, vis, m, n, i, j + 1); path += right; } if(i >= 1 && mat[i - 1][j] == mat[i][j]) // haut { up = dfs(mat, vis, m, n, i - 1, j); path += up; } if(j >= 1 && mat[i][j - 1] == mat[i][j]) // gauche { left = dfs(mat, vis, m, n, i, j - 1); path += left; } ans = max(ans, 1 + path); return ans; } // dfs() // Returns length of the longest path beginning with any cell int findLongest(const vector> &mat, const int m, const int n) { int longest = 1; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { auto visited = vector>(m, vector(n, false)); int ans = dfs(mat, visited, m, n, i, j); // Après l'appel à dfs(), toutes les cases de même altitude // que mat[i][j] sont marquées comme visitées. if(ans > longest) // On vient de trouver un plateau plus long { longest = ans; for(int ii = 0; ii < m; ii++) { for(int jj = 0; jj < n; jj++) { if(visited[ii][jj]) solution[ii][jj] = '*'; else solution[ii][jj] = '.'; } } } } } return longest; } // findLongest() int main() { // lecture entrée int m = 0, n = 0; // hauteur, largeur cin >> m >> n; auto a = vector>(m, vector(n, 0)); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) cin >> a[i][j]; solution = vector>(m, vector(n, '.')); // affichage /*for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) printf("%3d ", a[i][j]); cout << '\n'; }*/ cout << findLongest(a, m, n) << '\n'; for(int i = 0; i < m; i++, cout << '\n') for(int j = 0; j < n; j++) cout << solution[i][j] << ' '; return 0; } // main()