Codeforces 919C - Seat Arrangements

传送门：http://codeforces.com/contest/919/problem/C

给出一张n×m的座位表（有已占座位和空座位），请选择同一行（或列）内连续的k个座位。求选择的方法数。

Hack：首先，若k=1，则所有的空座位均可选，方法数即为空座位数。

对于某一行（或列）中连续的len个座位，选择的方法数为len-k+1。

于是，分别逐行、逐列地统计，求出答案。参考程序如下：

#include <stdio.h>

#define MAX_N 2000

char map[MAX_N][MAX_N];

int row[MAX_N][MAX_N], col[MAX_N][MAX_N];

int main(void)

{

    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i < n; i++) {

        getchar();

        for (int j = ; j < m; j++)

            map[i][j] = getchar();

    }

    int ans = ;

    if (k == ) {

        for (int i = ; i < n; i++) {

            for (int j = ; j < m; j++)

                if (map[i][j] == '.') ans++;

        }

        printf("%d\n", ans);

        return ;

    }

    //pass by row

    for (int i = ; i < n; i++) {

        int len = , cnt = ;

        for (int j = ; j < m; j++) {

            if (map[i][j] == '*') {

                if (len) row[i][cnt++] = len;

                len = ;

            }

            else len++;

        }

        if (len) row[i][cnt++] = len;

    }

    //pass by column

    for (int j = ; j < m; j++) {

        int len = , cnt = ;

        for (int i = ; i < n; i++) {

            if (map[i][j] == '*') {

                if (len) col[j][cnt++] = len;

                len = ;

            }

            else len++;

        }

        if (len) col[j][cnt++] = len;

    }

    for (int i = ; i < n; i++) {

        for (int j = ; row[i][j] != ; j++)

            if (row[i][j] >= k) ans += row[i][j] - k + ;

    }

    for (int i = ; i < m; i++) {

        for (int j = ; col[i][j] != ; j++)

            if (col[i][j] >= k) ans += col[i][j] - k + ;

    }

    printf("%d\n", ans);

    return ;

}

巴特西

Codeforces 919C - Seat Arrangements

最新文章

热门文章