# 12593 - D-Lamp
## 題解:
用prefix sum去算每個點的四個方向的總和
一開始我是開四個二維陣列, 但是會MLE, 所以改只用一個

**Note :** answer要減3是因為lamp那點會重複計算到
## Code:

#include <stdio.h>
#include <string.h>
#define max(a, b) (a > b ? a : b)
#define N 2500 + 5

int h, w;
int sum[N][N], ans[N][N];
char g[N][N]; // graph

int main(){
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; i++)
        scanf("%s", g[i]);
    // up
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if(g[i][j] == '.')
                sum[i][j] = (i == 0 ? 1 : sum[i - 1][j] + 1);
            ans[i][j] += sum[i][j];
        }
    }
    // down
    memset(sum, 0, sizeof(sum));
    for (int i = h - 1; i >= 0; i--){
        for (int j = w - 1; j >= 0; j--){
            if(g[i][j] == '.')
                sum[i][j] = (i == h - 1 ? 1 : sum[i + 1][j] + 1);
            ans[i][j] += sum[i][j];
        }
    }
    // left
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if(g[i][j] == '.')
                sum[i][j] = (j == 0 ? 1 : sum[i][j - 1] + 1);
            ans[i][j] += sum[i][j];
        }
    }
    // right
    memset(sum, 0, sizeof(sum));
    for (int i = h - 1; i >= 0; i--){
        for (int j = w - 1; j >= 0; j--){
            if(g[i][j] == '.')
                sum[i][j] = (j == w - 1 ? 1 : sum[i][j + 1] + 1);
            ans[i][j] += sum[i][j];
        }
    }
    int max = 0;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            ans[i][j] -= 3;
            max = max(max, ans[i][j]);
        }
    }
    printf("%d\n", max);
    return 0;
}

###### tags: `NTHUOJ`