pascal题目
题目描述
小猪在小学中认识了很多的字，终于会写一点作文了。某天小猪买了一张方格稿纸来写作文，n行m列，形状如下所示：
上图中n=m=5。
某天小猪的邻居小小猪来小猪家玩，用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色，如下图所示。
小猪不能责怪小小猪。作文写不成了，他觉得很无聊，就开始数里面有多少魔幻方阵。
如果稿纸中一个k×k的正方形区域满足以下两个条件，那么它就是魔幻方阵：
1．黑白格子的数量差不能超过1；
2．k不能小于2。
上图染色后的方格稿纸共有9个魔幻方阵（6个2×2的魔幻方阵，3个3×3的魔幻方阵），现在请你帮小猪求出他被染色的稿纸里面有多少个魔幻方阵。
输入
第一行有二个正整数n和m（互相之间以一个空格分隔），表示稿纸共有n行m列。
接下来n行，每行有m个0或1的整数（互相之间以一个空格分隔），代表每个格子的颜色。如果这个数是1则为黑色，是0则为白色。
输出
仅有一行，该行只有一个整数，表示稿纸中魔幻方阵的个数。
样例输入
5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1
样例输出
9
提示
【数据规模】
50%的数据，1≤n≤10，1≤m≤10；
75%的数据，1≤n≤180，1≤m≤180；
100%的数据，1≤n≤300，1≤m≤300。 展开
【算法分析】模拟（下面只是我自己的算法，不保证有其他更简便的算法哦、、、）
使用数组f[i,j]通过递归算法记录从(1,1)开始的i*j的矩形内数字1的个数
即可表示出从(i,j)开始的k*k的矩形内数字1的个数t，计算k²-t与t的大小关系，从而判断出该矩形是否是魔幻方阵
---------------------------------------------------------------------------------------------------------------------
下面大概说明下第二步的方法：
如图红色矩形内1的个数即可表示为f[4,4]-f[4,1]-f[1,4]+f[1,1]（f[1,1]被多减了一次，所以最后还要加上去）
从而归纳出从(i,j)开始的k*k的矩形内数字1的个数t:=f[i+k-1,j+k-1]-f[i+k-1,j-1]-f[i-1,j+k-1]+f[i-1,j-1]
【参考程序】
var n,m,t,i,j,k,sum:longint;
f,g:array[0..301,0..301]of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
begin
readln(n,m);
if(n=1)or(m=1)then
begin
writeln(0);
halt;
end;
for i:=1 to n do
for j:=1 to m do
read(g[i,j]);
for i:=1 to n do
for j:=1 to m do
inc(f[i,j],f[i-1,j]+f[i,j-1]-f[i-1,j-1]+g[i,j]);
for k:=2 to min(m,n) do
for i:=1 to n-k+1 do
for j:=1 to m-k+1 do
begin
t:=f[i+k-1,j+k-1]-f[i+k-1,j-1]-f[i-1,j+k-1]+f[i-1,j-1];
if abs(k*k-2*t)<=1 then
inc(sum);
end;
writeln(sum);
end.
【评测结果】╮(╯▽╰)╭
