hdu5024-Wang Xifeng's Little Plot

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

 #include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std; char a[][]= {};
int down[][]= {};
int up[][]= {}; int cnt[][][]= {};
int n;
int dx[]= {-,,-, };
int dy[]= {-,, ,-};
int dfs(int curx,int cury,int num)
{
if(curx< || cury< || curx>=n || cury>=n)
return ;
int &ans=cnt[curx][cury][num];
if(a[curx][cury]=='#')
return ans=;
return ans=+dfs(curx+dx[num],cury+dy[num],num);
} int getMax()
{
int ans=;
for(int i=; i<n; i++)
for(int j=; j<n; j++)
{
ans=max(ans,down[i][j]+up[i][j]-);
}
return ans;
} int main()
{
freopen("in.txt","r",stdin); while(scanf("%d",&n),n)
{
memset(down,,sizeof down);
memset(up,,sizeof up);
memset(cnt,,sizeof cnt);
for(int i=; i<n; i++)
scanf("%s",a[i]); for(int i=; i<n; i++)
for(int j=; j<n; j++)
{
if(a[i][j]=='#')
{
up[i][j]=down[i][j]=; }
else
{
up[i][j]=down[i][j]=;
if(i!=)
up[i][j]=up[i-][j]+;
if(j!=)
down[i][j]=down[i][j-]+;
}
} int ans=;
ans=max(ans,getMax()); memset(down,,sizeof down);
memset(up,,sizeof up);
for(int i=n-; i>=; i--)
for(int j=n-; j>=; j--)
{
if(a[i][j]=='#')
{
up[i][j]=down[i][j]=;
}
else
{
up[i][j]=down[i][j]=;
if(i!=n-)
up[i][j]=up[i+][j]+;
if(j!=n-)
down[i][j]=down[i][j+]+;
}
} ans=max(ans,getMax()); //---------------------------
memset(down,,sizeof down);
memset(up,,sizeof up);
for(int i=; i<n; i++)
for(int j=n-; j>=; j--)
{
if(a[i][j]=='#')
{
up[i][j]=down[i][j]=;
}
else
{
up[i][j]=down[i][j]=;
if(i!=)
up[i][j]=up[i-][j]+;
if(j!=n-)
down[i][j]=down[i][j+]+;
}
} ans=max(ans,getMax());
//-------------------------------
memset(down,,sizeof down);
memset(up,,sizeof up);
for(int i=n-; i>=; i--)
for(int j=; j<n; j++)
{
if(a[i][j]=='#')
{
up[i][j]=down[i][j]=;
}
else
{
up[i][j]=down[i][j]=;
if(i!=n-)
up[i][j]=up[i+][j]+;
if(j!=)
down[i][j]=down[i][j-]+;
}
} ans=max(ans,getMax());
//-------------------------------------------------- for(int i=; i<n; i++)
for(int j=; j<n; j++)
{
for(int num=; num<; num++)
{
dfs(i,j,num);
}
} for(int i=; i<n; i++)
for(int j=; j<n; j++)
{
ans=max(ans,cnt[i][j][]+cnt[i][j][]-);
ans=max(ans,cnt[i][j][]+cnt[i][j][]-);
ans=max(ans,cnt[i][j][]+cnt[i][j][]-);
ans=max(ans,cnt[i][j][]+cnt[i][j][]-);
} cout<<ans<<endl;
}
return ;
}
上一篇:让Lua自己把文件夹下面的所有文件自动加载起来吧


下一篇:[异常记录-12]Web Deploy部署:未能连接到远程计算机,请确保在远程计算机上安装了 Web Deploy 并启动了所需的进程("Web Management Service")