返回信息流输入一个二维数组表示的地图，图上有：0=空地，1=灯，2=墙。如下图示例：
2 0 2 1 0 0 2 2 0 0
2 1 0 1 0 0 1 0 1 0
0 1 0 0 0 2 2 0 1 0
0 0 0 2 1 2 0 1 1 0
0 0 2 1 1 1 1 0 1 0
2 0 1 1 0 0 0 0 2 1
1 0 0 0 2 0 0 2 1 0
2 0 0 2 0 0 0 0 2 1
1 0 2 1 1 1 0 0 0 0
0 0 0 0 2 1 0 1 0 0
一个人可以站在某个空地位置，往上下左右看（斜线不行），看到他所在位置的横竖排所有的灯，但如果有墙的话就会挡住视线，所以看不到墙后面的灯。比如在（0,1）位置的空地，竖排可以看到2个灯，但横排两边都是墙，所以一个灯都看不到，故人在该位置能看到的总灯数为2.
问题：输入一个特定的地图，找出一个空地位置，使人可以看到最多数量的灯，返回该空地的坐标。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89469同步于 2016/3/31
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教一个算法题
wan751
2016/3/31镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
直接思路：
1. 循环遍历二维数组，判断a[i][j]==0
2. ==0：从当前位置分别向上下左右遍历，统计num
3. 如果num > max; max = num
注意的地方
1. 输入数组为空，a[0][0],a[1][1],a[2][2]
2. 在最外圈的可能会越界
自己实现了一下，果然是想的简单，注释的地方都是自己思考岔路的地方。
有想法了还是自己动手实现一下比较稳妥。各种问题出现。
明白了，谢谢哈！
【 在 Wizmann 的大作中提到: 】
: 预处理前辍和，算上下左右4次就行。预处理时间O(n ^ 2)，空间O(n ^ 2)。每次查询O(1)。
#include<stdio.h>
#define GROUND 0
#define LAMP 1
#define WALL 2
int main()
{
int map[101][101];//地图最大尺度为100 * 100
int tempLamp = 0,maxLamp = 0;
int mapLength,mapWidth;
int i,j,k,l;
int result_x = 0,result_y = 0;
printf("请输入地图的长度和宽度：");
scanf("%d%d",&mapLength,&mapWidth);
for(i = 1; i <= mapLength; i++)
for(j = 1; j <= mapWidth; j++)
{
scanf("%d",&map[i][j]);
}
for(i = 1; i <= mapLength; i++)
for(j = 1; j <= mapWidth; j++)
{
if(map[i][j] == GROUND)
{
for(k = i + 1; k <= mapLength; k++)
{
if(map[k][j] == LAMP)
{
tempLamp++;
}
else if(map[k][j] == WALL)
{
break;
}
}
for(k = i - 1; k >= 1; k--)
{
if(map[k][j] == LAMP)
{
tempLamp++;
}
else if(map[k][j] == WALL)
{
break;
}
}
for(l = j + 1; l <= mapWidth; l++)
{
if(map[i][l] == LAMP)
{
tempLamp++;
}
else if(map[i][l] == WALL)
{
break;
}
}
for(l = j - 1; l >= 1; l--)
{
if(map[i][l] == LAMP)
{
tempLamp++;
}
else if(map[i][l] == WALL)
{
break;
}
}
if(tempLamp > maxLamp)
{
result_x = i;
result_y = j;
maxLamp =tempLamp;
}
tempLamp = 0;
}
}
if(result_x == 0 && result_y == 0)
printf("no lamp we can see!\n");
else
printf("one of the max location is %d %d\nthe maxLamp is %d\n",result_x,result_y,maxLamp);
return 0;
}
看看行不？暴力解法
我做了个实验，如果地图里的墙很密集，那么暴力破解只会比n^2高一点，此时暴力会优于2楼的算法，因为2楼的算法应该是5n^2。但如果墙很稀疏，那暴力破解就接近n^3, 比不上2楼的算法了。
【 在 jxfzqyxxz 的大作中提到: 】
: #include<stdio.h>
: #define GROUND 0
: #define LAMP 1
: ...................
1.按行，找1和0的集合，累加，记住其中的0，即a[01]和为0 a[04]与a[05]和为1（省去一次计算），可以得出一个矩阵
2.按列，找1和0的集合，累加，可以得出一个矩阵
3.两矩阵相加，遍历得出结果