J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

This takes all submatrices, filters them based on whether their 4 corners sorted matches the target sorted, and returns the sum.

The two parts that required the most experimentation to golf were:

• (;/-#:i.4)&{ The phrase to pull the 4 corners from a matrix. It generates the numbers 0 through 3 in binary, negates the ones, and uses those as a 2d index for "take" {:
  • 0 0 top left corner
  • 0 _1 top right corner
  • _1 0 bottom left corner
  • _1 _1 bottom right corner
• [:g@|:&>g=.[:;@,<@(1}.<\)\. The phrase to generate all submatrixes. It has two parts:
  • <@(1}.<\)\. First we generate all possible heights for valid full width rectangles. We do this by calculating all prefixes of all suffixes, deleting the first element of each prefix list, because it has dimension 1. [:;@, is a technicality required to keep the list flat. Note that we also save this phrase as g...
  • [:g@|:&> We now reapply g to the transpose of every result from the first step, generating all the possible widths for each possible height. Together, these step generate all possible widths for every possible height rectangle, accounting for all possible submatrices.

J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

This takes all submatrices, filters them based on whether their 4 corners sorted matches the target sorted, and returns the sum.

The two parts that required the most experimentation to golf were:

• (;/-#:i.4)&{ The phrase to pull the 4 corners from a matrix. It generates the numbers 0 through 3 in binary, negates the ones, and uses those as a 2d index for "take" {:
  • 0 0 top left corner
  • 0 _1 top right corner
  • _1 0 bottom left corner
  • _1 _1 bottom right corner
• [:g@|:&>g=.[:;@,<@(1}.<\)\. The phrase to generate all submatrixes. It has two parts:
  • <@(1}.<\)\. First we generate all possible heights for valid full width rectangles. We do this by calculating all prefixes of all suffixes, deleting the first element of each prefix list, because it has dimension 1. [:;@, is a technicality required to keep the list flat. Note that we also save this phrase as g...
  • [:g@|:&> We now reapply g to the transpose of every result from the first step, generating all the possible widths for each possible height. Together, these step generate all possible widths for every possible height rectangle, accounting for all possible submatrices.

J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

alternate approach, 72 bytes

+/@,@;@(((-:&(/:~)&,({@;~0 _1)&{)&>~<)#&,[)~[:g@|:&>g=.a:-.~[:,(1}.<\)\.

Try it online!

J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

This takes all submatrices, filters them based on whether their 4 corners sorted matches the target sorted, and returns the sum.

The two parts that required the most experimentation to golf were:

• (;/-#:i.4)&{ The phrase to pull the 4 corners from a matrix. It generates the numbers 0 through 3 in binary, negates the ones, and uses those as a 2d index for "take" {:
  • 0 0 top left corner
  • 0 _1 top right corner
  • _1 0 bottom left corner
  • _1 _1 bottom right corner
• [:g@|:&>g=.[:;@,<@(1}.<\)\. The phrase to generate all submatrixes. It has two parts:
  • <@(1}.<\)\. First we generate all possible heights for valid full width rectangles. We do this by calculating all prefixes of all suffixes, deleting the first element of each prefix list, because it has dimension 1. [:;@, is a technicality required to keep the list flat. Note that we also save this phrase as g...
  • [:g@|:&> We now reapply g to the transpose of every result from the first step, generating all the possible widths for each possible height. Together, these step generate all possible widths for every possible height rectangle, accounting for all possible submatrices.

J, ^{75 72 71 70} 68 bytes

+/@,@;@((-:&(/:~)"#.(,{@;~0 _1)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

alternate approach, 72 bytes

+/@,@;@(((-:&(/:~)&,({@;~0 _1)&{)&>~<)#&,[)~[:g@|:&>g=.a:-.~[:,(1}.<\)\.

Try it online!

J, ^{75 72 71 70 68} 66 bytes

+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

Try it online!

alternate approach, 72 bytes

+/@,@;@(((-:&(/:~)&,({@;~0 _1)&{)&>~<)#&,[)~[:g@|:&>g=.a:-.~[:,(1}.<\)\.

Try it online!