bzoj1661[Usaco2006 Nov]Big Square 巨大正方形

题意:

n*n的图中有一些J点,一些B点和一些空白点,问在空白点添加一个J点所能得到的有4个J点组成最大正方形面积。n≤100。

题解:

枚举两个点,然后根据这两个点组成的边尝试在4个上下两个方向组成四边形。

代码:

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
using namespace std; char graph[maxn][maxn]; int n,ans;
int main(){
scanf("%d",&n); inc(i,,n)scanf("%s",graph[i]+);
inc(i,,n)inc(j,,n)if(graph[i][j]=='J'){
inc(k,i+,n){
inc(l,,j){
int cnt=;
if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;
int x=l-j,y=k-i;
if(k-x>n||l+y>n||graph[k-x][l+y]=='B')goto jump1; if(graph[k-x][l+y]=='J')cnt++;
if(i-x>n||j+y>n||graph[i-x][j+y]=='B')goto jump1; if(graph[i-x][j+y]=='J')cnt++;
if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
jump1:;
if(k+x<||l-y<||graph[k+x][l-y]=='B')goto jump2; if(graph[k+x][l-y]=='J')cnt++;
if(i+x<||j-y<||graph[i+x][j-y]=='B')goto jump2; if(graph[i+x][j-y]=='J')cnt++;
if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
jump2:;
}
inc(l,j+,n){
int cnt=;
if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;
int x=l-j,y=k-i;
if(k-x<||l+y>n||graph[k-x][l+y]=='B')goto jump3; if(graph[k-x][l+y]=='J')cnt++;
if(i-x<||j+y>n||graph[i-x][j+y]=='B')goto jump3; if(graph[i-x][j+y]=='J')cnt++;
if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
jump3:;
if(k+x>n||l-y<||graph[k+x][l-y]=='B')goto jump4; if(graph[k+x][l-y]=='J')cnt++;
if(i+x>n||j-y<||graph[i+x][j-y]=='B')goto jump4; if(graph[i+x][j-y]=='J')cnt++;
if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
jump4:;
}
}
}
printf("%d",ans); return ;
}

20161023

最新文章

  1. CanvasWebgl项目介绍
  2. vm.max_map_count
  3. Have Fun with Numbers及循环链表(约瑟夫问题)
  4. bash魔法堂:History用法详解
  5. 关于iphone 6 ios8网站背景图片错乱的问题解决办法
  6. F2工作流引擎模型
  7. 关于NMF(Non-negative Matrix Factorization )
  8. Linux每天定时重启Tomcat服务
  9. java中图片文件的传输及显示(Socket以及ServerSocket演示)
  10. 【转】【C#】C#重绘windows窗体标题栏和边框
  11. JVM的生命周期
  12. JavaScript编码规范[百度]
  13. 使用xml及java代码混合的方式来设置图形界面
  14. 【Leetcode】Same Tree
  15. mac系统连接android电话
  16. Network view
  17. 【POJ2823】Sliding Window
  18. 网关 php-cgi fastcgi phpfpm
  19. Srtuts2实现登录界面(不连接数据库)报错(一)
  20. LODOP中ADD_PRINT_TABLE、HTM、HTML表格自动分页测试

热门文章

  1. 求求你,别问了,Java字符串是不可变的
  2. fork,vfork和clone底层实现
  3. Spring Data 教程 - Redis
  4. Day10-微信小程序实战-交友小程序-自定义callPhone 和copyText组件
  5. IDEA解决SVN频繁弹出登录框
  6. C++的逗号运算符
  7. 入门大数据---Spark整体复习
  8. javaScript的三种储存方式
  9. Docker(六)容器数据卷
  10. Spring笔记(3) - debug源码AOP原理解析