Then the N × N matrix follows.
The input ends with N = 0.
Output For each test case, print the maximum length of the road which Wang Xifeng could find to locate Baoyu and Baochai's rooms. A road's length is the number of '.'s it includes. It's guaranteed that for any test case, the maximum length is at least 2.
Sample Input
3
#.#
##.
..#
3
...
##.
..#
3
...
###
..#
3
...
##.
...
0
Sample Output
3
4
3
5
题意：找到一个最长的L型
思路：把L拆成两个直线，枚举所有的情况，记忆化搜索
#include
#include
#include
#include
using namespace std; const int maxn = 110; int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1}; int n, f[maxn][maxn][8]; char g[maxn][maxn]; int dfs(int x, int y, int dir) { if (f[x][y][dir] != -1) return f[x][y][dir]; if (g[x+dx[dir]][y+dy[dir]] == '.') return f[x][y][dir] = 1 + dfs(x+dx[dir], y+dy[dir], dir); else return f[x][y][dir] = 1; } int main() { while (scanf("%d", &n) != EOF && n) { memset(f, -1, sizeof(f)); memset(g, 0, sizeof(g)); for (int i = 1; i <= n; i++) scanf("%s", g[i]+1); int ans = -1; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (g[i][j] == '.') { ans = max(ans, dfs(i, j, 0) + dfs(i, j, 2) - 1); ans = max(ans, dfs(i, j, 1) + dfs(i, j, 2) - 1); ans = max(ans, dfs(i, j, 1) + dfs(i, j, 3) - 1); ans = max(ans, dfs(i, j, 0) + dfs(i, j, 3) - 1); ans = max(ans, dfs(i, j, 4) + dfs(i, j, 5) - 1); ans = max(ans, dfs(i, j, 4) + dfs(i, j, 6) - 1); ans = max(ans, dfs(i, j, 7) + dfs(i, j, 5) - 1); ans = max(ans, dfs(i, j, 7) + dfs(i, j, 6) - 1); } printf("%d\n", ans); } return 0; }