2491 玉蟾宫
2018-06-17 22:47:06来源:未知 阅读 ()
2491 玉蟾宫
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们每人给你S两银子。
第一行两个整数N,M,表示矩形土地有N行M列。
接下来N行,每行M个用空格隔开的字符'F'或'R',描述了矩形土地。
输出一个整数,表示你能得到多少银子,即(3*最大'F'矩形土地面积)的值。
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
45
对于50%的数据,1<=N,M<=200
对于100%的数据,1<=N,M<=1000
来源:Nescafe 20
分类标签 Tags 点此展开
1 #include<cstdio> 2 3 #include<iostream> 4 using namespace std; 5 int n,m,ans; 6 char x; 7 int a[1001][1001],h[1001],leftt[1001],rightt[1001]; 8 int main() 9 { 10 scanf("%d%d",&n,&m); 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=m;j++) 13 { 14 cin>>x; 15 if(x=='R') a[i][j]=1;//1代表有障碍,不能延伸了 16 } 17 for(int j=1;j<=m;j++)//初始化 18 { 19 leftt[j]=1; 20 rightt[j]=m; 21 } 22 for(int i=1;i<=n;i++)//枚举每一行 23 { 24 int l=0,r=m+1;//l向左第一个碰到的障碍,r向右第一个碰到的障碍 25 for(int j=1;j<=m;j++)//从左往右枚举每一列,确定l 26 { 27 if(a[i][j])//当前点是障碍 28 { 29 l=j;//更新向左碰到的第一个障碍 30 h[j]=0;//自本行以下子矩阵高度重新计数 31 leftt[j]=1;//因为left只有一维且以列为下标,所以下一次再用到left[j]是下一行,也就是a[i+1][j],那么由于第i行的阻断,第i+1行不能与前面连成一个矩阵,所以置为最初条件 32 } 33 else//当前点不是障碍,可以参与组成矩阵 34 { 35 h[j]++;//当前列高度+1 36 leftt[j]=max(leftt[j],l+1);//left[i]在更新之前还是第i-1行的结果,所以要从第i-1行和第i行中取大。l+1是因为l存的是R的位置,矩形延伸不能到有障碍的地方 37 } 38 } 39 for(int j=m;j>=1;j--)//同上更新r,确定向右找到的第一个R 40 { 41 if(a[i][j]) 42 { 43 r=j; 44 rightt[j]=m; 45 } 46 else 47 rightt[j]=min(rightt[j],r-1); 48 ans=max(ans,(rightt[j]-leftt[j]+1)*h[j]); 49 } 50 } 51 printf("%d",ans*3); 52 }
搜索代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=1001; 6 const int maxn=0x7fffffff; 7 int map[MAXN][MAXN]; 8 int vis[MAXN][MAXN]; 9 int xx[5]={-1,+1,0,0}; 10 int yy[5]={0,0,-1,+1}; 11 int ans=-1; 12 int maxnnow; 13 int n,m; 14 void dfs(int x,int y) 15 { 16 vis[x][y]=1; 17 for(int i=0;i<4;i++) 18 { 19 int wx=x+xx[i]; 20 int wy=y+yy[i]; 21 if(vis[wx][wy]==0&&map[wx][wy]==0&&wx>0&&wx<=n&&wy>0&&wy<=m) 22 { 23 maxnnow++; 24 dfs(wx,wy); 25 if(maxnnow>ans) 26 ans=maxnnow; 27 maxnnow=0; 28 } 29 } 30 } 31 int main() 32 { 33 34 scanf("%d%d",&n,&m); 35 for(int i=1;i<=n;i++) 36 { 37 for(int j=1;j<=m;j++) 38 { 39 char c; 40 //scanf("%d",&c); 41 cin>>c; 42 if(c=='R') 43 map[i][j]=1; 44 else 45 map[i][j]=0; 46 } 47 } 48 for(int i=1;i<=n;i++) 49 { 50 for(int j=1;j<=m;j++) 51 { 52 if(vis[i][j]==0) 53 { 54 dfs(i,j); 55 } 56 } 57 } 58 printf("%d",ans*3); 59 return 0; 60 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash