Maximum Connected Triple
Autumn Tournament (2007)
Submission name: maxi.cpp
Problem summary
Choose three distinct cells in a rectangular grid. They must form one side-connected group: every selected cell shares a side with at least one other selected cell. Maximize their sum.
Input
m n, followed by m rows of n positive values.
Output
The maximum sum of a valid triple.
Constraints
1 < m,n < 10; each cell contains a positive integer below 100.
Worked example
Original statement sample.
Input
2 2 1 3 2 4
Output
9
Solution analysis
- Any connected group of three grid cells is a path of two edges: either a straight line or an L. One cell is adjacent to both others. Enumerate that middle cell, then every pair of distinct directions among up, down, left and right.
- Reject a direction pair if either neighboring cell lies outside the grid. Otherwise add the middle value and its two neighbors, and update the maximum. This enumerates all orientations without needing separate shape-specific code.
- In the 2×2 sample, choose values 3,4,2. The cell containing 4 touches the other two, and their sum is 9. Choosing only consecutive cells in a row would miss this L-shaped optimum.
Why it works
Every valid three-cell group has a cell adjacent to both remaining cells, so it is examined when that cell is the middle. Conversely every accepted direction pair produces three distinct connected cells. Taking the maximum over exactly these candidates is correct.
Watch out. Do not count the same neighbor twice or use diagonal adjacency. The selected cells need not all lie in one row or column.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int rows,columns;
cin>>rows>>columns;
vector<vector<int>>grid(rows,vector<int>(columns));
for(auto&row:grid){
for(int&value:row){
cin>>value;
}
}
array<int,4>dr{-1,1,0,0};
array<int,4>dc{0,0,-1,1};
int answer=0;
for(int r=0;r<rows;r++){
for(int c=0;c<columns;c++){
for(int a=0;a<4;a++){
for(int b=a+1;b<4;b++){
int r1=r+dr[a],c1=c+dc[a];
int r2=r+dr[b],c2=c+dc[b];
if(r1>=0&&r1<rows&&c1>=0&&c1<columns&&r2>=0&&r2<rows&&c2>=0&&
c2<columns){
// Every connected triple has one such middle cell.
answer=max(answer,grid[r][c]+grid[r1][c1]+grid[r2][c2]);
}
}
}
}
}
cout<<answer<<'\n';
}