首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。