算法1:暴力枚举
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char g[110][110];
int main()
{
int r, c, k;
cin >> r >> c >> k;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> g[i][j];
int res = 0;
for (int i = 0; i < r; i++)
{
int cnt = 0;
for (int j = 0; j < c; j++)
{
if (g[i][j] == '.')
{
while (g[i][j] == '.')
{
cnt++;
j++;
}
if (cnt >= k)
res += cnt - k + 1;
}
cnt = 0;
}
}
for (int i = 0; i < c; i++)
{
int cnt = 0;
for (int j = 0; j < r; j++)
{
if (g[j][i] == '.')
{
while (g[j][i] == '.')
{
cnt++;
j++;
}
if (cnt >= k)
res += cnt - k + 1;
}
cnt = 0;
}
}
if (k == 1)
res /= 2;
cout << res;
return 0;
}
算法2:DFS
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int r, c, k;
char g[110][110];
int dx[2] = {0, 1}, dy[2] = {1, 0}; // 向右以及向下
int res;
void dfs(int x, int y, int d, int len)
{
if (len > k)
{
res++;
return;
}
if (g[x][y] == '#' || x < 0 || x >= r || y < 0 || y >= c)
return;
dfs(x + dx[d], y + dy[d], d, len + 1);
}
int main()
{
cin >> r >> c >> k;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> g[i][j];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (g[i][j] == '.')
dfs(i, j, 0, 1), dfs(i, j, 1, 1);
if (k == 1)
res /= 2;
cout << res;
return 0;
}