HDU 5024 Wang Xifeng's Little Plot（暴力列挙＋でたらめ）

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5024
Problem Description
『Dream of the Red Chamer』is one of the Four Greast Class Novels of Chinese literature，and it is command regarded as the best one.This novel was created in Qyness the ty，Buxiversity。and that part of current version was written by Gao E.The re is a heart breaking story saying that after Cao Xueqin died、Cao's wife burned the last 40 chapter mauscript for heating because she was desperately poor.This story was proved a rumor couble of days ago because someone foveral pages of the original last 40 pterry 
In the novel，Wang Xifeng was in charge of Da Guan Yun，where people of Jiafamimimimimimimimimimimimimimimid.It was mentioned inthe newly recovered pages at Wang Xfinininininined to arrararangerorooms forJBaohehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehehe、and Xue Baochai was beautiful and very capable、Wang Xifreeng didn't want Jia Baoyu to mary Xue Baochai、in case that Xue Baochai might Tare place.So、Wang Xifung want Baoyu's room and Baochai's rocated to located to to to to to to baochated able of road、and and and and and road。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 ninety degree.The e e is a map of Da Guawan the the novestreone，End。aralways arging about the location of Baoyu's room and Baochai's room.Now you can solive this big problem and then becompe a great redist.
 
Input
The map of Da Gugn Yuuwan is represented by a matix of characters'''and'\\\摨;\\25708;\放\放\\\\\\\\?\\\\\\\\\\\\\\uth，south-east，east and north-east.
The re are several test cases.
For each case，the first line is an integer N(0<=N==100)、meaning the map is a N× N matix.
The n the N× N matix 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 Grant the atcast
 
Sample Input

   
   
   
   

    
    
    
    3
#.#
##.
..#
3
...
##.
..#
3
...
###
..#
3
...
##.
...
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
4
3
5
   
   
   
   

 
ソurce
2014 ACM/ICPC Asia Regional Guangzhou Online
件名:
与えられた図の中で、「.」は実行可能な道を表しています。
考え方:
暴力列挙の各点の8つの方向の実現可能な道の距離、90度の回転だけなため、私達は8つの方向を2回の列挙に分けます！これで90度は保証できます。各「.」の実行可能なパスを列挙してから、その中の一番遠い二つのパスを足し算すればいいです。（つまり、一つ一つを列挙してカーブするところです）。
コードは以下の通りです

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define MAXN 117
using namespace std;
char mm[MAXN][MAXN];
int k;
int xx[8]= {0,1,0,-1,-1,1,1,-1};
int yy[8]= {1,0,-1,0,1,1,-1,-1};
int main()
{
    int n;
    int re1[8],re2[8];
    while(~scanf("%d",&n) && n)
    {
        memset(mm,0,sizeof(mm));
        int maxx = -1;
        for(int i = 0; i < n; i++)
        {
            scanf("%s",mm[i]);
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                memset(re1,0,sizeof(re1));
                if(mm[i][j] == '.')
                {
                    for(int l = 0; l < 4; l++)
                    {
                        int t1 = i, t2 = j;
                        while(1)
                        {
                            if(mm[t1][t2]=='.')
                            {
                                re1[l]++;
                            }
                            else
                                break;
                            t1+=xx[l], t2+=yy[l];
                        }
                    }
                    sort(re1,re1+4);
                    if(re1[2]+re1[3]> maxx)
                        maxx = re1[2]+re1[3];
                }
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                memset(re2,0,sizeof(re2));
                if(mm[i][j] == '.')
                {
                    for(int l = 4; l < 8; l++)
                    {
                        int t1 = i, t2 = j;
                        while(1)
                        {
                            if(mm[t1][t2]=='.')
                            {
                                re2[l-4]++;
                            }
                            else
                                break;
                            t1+=xx[l], t2+=yy[l];
                        }
                    }
                    sort(re2,re2+4);
                    if(re2[2]+re2[3]> maxx)
                        maxx = re2[2]+re2[3];
                }
            }
        }
        printf("%d
",maxx-1);
    }
    return 0;
}