首页 > 代码库 > hdu5024-Wang Xifeng's Little Plot

hdu5024-Wang Xifeng's Little Plot

此题一开始用暴力做,后来发现斜着走的时候其实暴力不太好写,于是改用搜索写了

 

  1 #include <iostream>  2 #include <stdio.h>  3 #include <memory.h>  4 using namespace std;  5   6 char a[110][110]= {0};  7 int down[110][110]= {0};  8 int up[110][110]= {0};  9  10 int cnt[110][110][4]= {0}; 11 int n; 12 int dx[4]= {-1,1,-1, 1}; 13 int dy[4]= {-1,1, 1,-1}; 14 int dfs(int curx,int cury,int num) 15 { 16     if(curx<0 || cury<0 || curx>=n || cury>=n) 17         return 0; 18     int &ans=cnt[curx][cury][num]; 19     if(a[curx][cury]==#) 20         return ans=0; 21     return ans=1+dfs(curx+dx[num],cury+dy[num],num); 22 } 23  24  25 int getMax() 26 { 27     int ans=0; 28     for(int i=0; i<n; i++) 29         for(int j=0; j<n; j++) 30         { 31             ans=max(ans,down[i][j]+up[i][j]-1); 32         } 33     return ans; 34 } 35  36 int main() 37 { 38     freopen("in.txt","r",stdin); 39  40     while(scanf("%d",&n),n) 41     { 42         memset(down,0,sizeof down); 43         memset(up,0,sizeof up); 44         memset(cnt,0,sizeof cnt); 45         for(int i=0; i<n; i++) 46             scanf("%s",a[i]); 47  48         for(int i=0; i<n; i++) 49             for(int j=0; j<n; j++) 50             { 51                 if(a[i][j]==#) 52                 { 53                     up[i][j]=down[i][j]=0; 54  55                 } 56                 else 57                 { 58                     up[i][j]=down[i][j]=1; 59                     if(i!=0) 60                         up[i][j]=up[i-1][j]+1; 61                     if(j!=0) 62                         down[i][j]=down[i][j-1]+1; 63                 } 64             } 65  66         int ans=0; 67         ans=max(ans,getMax()); 68  69         memset(down,0,sizeof down); 70         memset(up,0,sizeof up); 71         for(int i=n-1; i>=0; i--) 72             for(int j=n-1; j>=0; j--) 73             { 74                 if(a[i][j]==#) 75                 { 76                     up[i][j]=down[i][j]=0; 77                 } 78                 else 79                 { 80                     up[i][j]=down[i][j]=1; 81                     if(i!=n-1) 82                         up[i][j]=up[i+1][j]+1; 83                     if(j!=n-1) 84                         down[i][j]=down[i][j+1]+1; 85                 } 86             } 87  88         ans=max(ans,getMax()); 89  90 //--------------------------- 91         memset(down,0,sizeof down); 92         memset(up,0,sizeof up); 93         for(int i=0; i<n; i++) 94             for(int j=n-1; j>=0; j--) 95             { 96                 if(a[i][j]==#) 97                 { 98                     up[i][j]=down[i][j]=0; 99                 }100                 else101                 {102                     up[i][j]=down[i][j]=1;103                     if(i!=0)104                         up[i][j]=up[i-1][j]+1;105                     if(j!=n-1)106                         down[i][j]=down[i][j+1]+1;107                 }108             }109 110         ans=max(ans,getMax());111 //-------------------------------112         memset(down,0,sizeof down);113         memset(up,0,sizeof up);114         for(int i=n-1; i>=0; i--)115             for(int j=0; j<n; j++)116             {117                 if(a[i][j]==#)118                 {119                     up[i][j]=down[i][j]=0;120                 }121                 else122                 {123                     up[i][j]=down[i][j]=1;124                     if(i!=n-1)125                         up[i][j]=up[i+1][j]+1;126                     if(j!=0)127                         down[i][j]=down[i][j-1]+1;128                 }129             }130 131         ans=max(ans,getMax());132 //--------------------------------------------------133 134         for(int i=0; i<n; i++)135             for(int j=0; j<n; j++)136             {137                 for(int num=0; num<4; num++)138                 {139                     dfs(i,j,num);140                 }141             }142 143         for(int i=0; i<n; i++)144             for(int j=0; j<n; j++)145             {146                 ans=max(ans,cnt[i][j][0]+cnt[i][j][2]-1);147                 ans=max(ans,cnt[i][j][0]+cnt[i][j][3]-1);148                 ans=max(ans,cnt[i][j][1]+cnt[i][j][3]-1);149                 ans=max(ans,cnt[i][j][1]+cnt[i][j][2]-1);150             }151 152         cout<<ans<<endl;153     }154     return 0;155 }

 

hdu5024-Wang Xifeng's Little Plot