# Base selection questions, C + + has just begun to learn, can someone give some ideas

2022-02-03 01:07:58

【 Problem description 】 The king rewarded the Dragon Slayer 4 A continuous fief , Please be there. nn Fief of （ The length of each fief is 11 The square of ） Within the scope of , Select... With at least one common edge connected to other fiefs 4 A fief . Each fief has a wealth value , Please help the warriors choose the fief , Make the value of wealth maximum .【 Input form 】 The first line is an integer n; below n That's ok , Each line is separated by a space n The value of the feudal wealth expressed as a positive integer ;【 Output form 】1 It's an integer ,4 The sum of the greatest wealth value of the fief .
【 The sample input 】5
1 1 1 1 1
1 1 1 2 1
1 1 2 2 3
1 1 1 1 1
1 1 1 1 1
【 Sample output 】
9
【 Sample explanation 】
The style of the four fiefs can be referred to “ tetris ”.
【 Standard for evaluation 】2<=n<20; Data assurance 4 The sum of the wealth of the fiefs is less than 2^31.

Refer to the answer 1：

This is similar to the shortest path problem , The algorithm is involved , Beginners c++ It's OK to do such a difficult problem

Refer to the answer 2：