HDU 5024 Wang Xifeng's Little Plot (枚舉 ＋ DFS記憶化搜索)
Wang Xifeng's Little Plot
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 513 Accepted Submission(s): 338
Problem Description
《Dream of the Red Chamber》(also 《The Story of the Stone》) is one of the Four Great Classical Novels of Chinese literature, and it is commonly regarded as the best one. This novel was created in Qing Dynasty, by Cao Xueqin. But the
last 40 chapters of the original version is missing, and that part of current version was written by Gao E. There is a heart breaking story saying that after Cao Xueqin died, Cao's wife burned the last 40 chapter manuscript for heating because she was desperately
poor. This story was proved a rumor a couple of days ago because someone found several pages of the original last 40 chapters written by Cao.
In the novel, Wang Xifeng was in charge of Da Guan Yuan, where people of Jia family lived. It was mentioned in the newly recovered pages that Wang Xifeng used to arrange rooms for Jia Baoyu, Lin Daiyu, Xue Baochai and other teenagers. Because Jia Baoyu was
the most important inheritor of Jia family, and Xue Baochai was beautiful and very capable , Wang Xifeng didn't want Jia Baoyu to marry Xue Baochai, in case that Xue Baochai might take her place. So, Wang Xifeng wanted Baoyu's room and Baochai's room to be
located at two ends of a road, and this road should be as long as possible. But Baoyu was very bad at directions, and he demanded that there could be at most one turn along the road from his room to Baochai's room, and if there was a turn, that turn must be
ninety degree. There is a map of Da Guan Yuan in the novel, and redists (In China English, one whose job is studying 《Dream of the Red Chamber》is call a "redist") are always arguing about the location of Baoyu's room and Baochai's room. Now you can solve this
big problem and then become a great redist.
Input
The map of Da Guan Yuan is represented by a matrix of characters '.' and '#'. A '.' stands for a part of road, and a '#' stands for other things which one cannot step onto. When standing on a '.', one can go to adjacent '.'s through
8 directions: north, north-west, west, south-west, south, south-east,east and north-east.
There are several test cases.
For each case, the first line is an integer N(0
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
Source
2014 ACM/ICPC Asia Regional Guangzhou Online
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5024
題目大意：一個n＊n的方陣，'.'為可行區域，'#'為障礙物，人在方陣中只可以直走或者轉90度彎，求方陣中只轉一次90度彎的最長可行區域個數
題目分析：90度彎有8種不同的情況，注意不要忘了斜著的直角，枚舉所有符合條件的轉彎方案再DFS（准確的說這裡枚舉的是轉彎點，因為後面DFS是從轉彎點開始往兩個呈90度的方向搜索的），DFS時用記憶化搜索，dp[x][y][dir]表示到點(x,y)且方向為dir時的可行區域的長度
#include
#include
#include
using namespace std;
int const MAX = 105;
//這裡方向不能改變
int dx[8] = {0, -1, 0, 1, -1, 1, 1, -1};
int dy[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dp[MAX][MAX][8], n, ans;
char map[MAX][MAX];
int DFS(int x, int y, int dir)
{
if(dp[x][y][dir] != -1)
return dp[x][y][dir];
if(map[x + dx[dir]][y + dy[dir]] == '.')
return dp[x][y][dir] = 1 + DFS(x + dx[dir], y + dy[dir], dir);
else
return dp[x][y][dir] = 1;
}
void cal(int x, int y, int d1, int d2)
{
ans = max(ans, DFS(x, y, d1) + DFS(x, y, d2) - 1);
}
int main()
{
while(scanf("%d", &n) != EOF && n)
{
ans = -1;
memset(dp, -1, sizeof(dp));
memset(map, 0, sizeof(map));
for(int i = 0; i < n; i++)
scanf("%s", map[i]);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(map[i][j] == '.')
for(int k = 0; k < 4; k++)
{
cal(i, j, k % 4, (k + 1) % 4);
cal(i, j, 4 + (k % 4), 4 + (k + 1) % 4);
}
printf("%d\n", ans);
}
}
