首页 > 代码库 > POJ 3251 Big Square
POJ 3251 Big Square
A quite challenging problem,最终看了题解才写出来,惭愧
/*Sample Input
6
J*J***
******
J***J*
******
**B***
******
Sample Output
4
*/
这道题里用到的几种思想还是值得我回味和思考的就是:
1、将复杂的等式用#define代替,不仅简洁而且时间复杂度较低
2、需要在输入的时候加入一个scanf来接收空格键,否则会出错
//这道题目主要是给定一个最大步数,让你输出你在二维空间中可以到达的位置,最后求最大能够形成的面积
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ok(a,b,c,d) (a>=0&&b>=0&&c>=0&&d>=0)
char map[201][201],enter;
int n,i,j,x,y,p,q,ans;
int main()
{
cin>>n;//输入这是n*n的正方形
for (i=1;i<=n;i++)
{
cin>>enter;//主要是为了吸收回车键(一开始没有注意到)
for (j=1;j<=n;j++)
cin>>map[i][j];
}
for (x=1;x<=n;x++)
for (y=1;y<=n;y++)
if (map[x][y]!=‘B‘)
for (i=n;i>=1;i--)
for(j=n;j>=y;j--)
{
p=i-x;q=j-y;
if (p*p+q*q<=ans)//一开始ans为多少也不知道啊?
continue;
if (map[i][j]==‘B‘||((map[i][j]==map[x][y])&&(map[x][y]!=‘J‘)))
continue;
if (ok(x-q,i-q,y+p,j+p)&&(map[x-q][y+p]==‘J‘)&&(map[i-q][j+p]==‘J‘)||ok(y-p,j-p,i+q,x+q)&&(map[x+q][y-p]==‘J‘)&&(map[i+q][j-p]==‘J‘))
ans=p*p+q*q;
}
printf("%d",ans);
return 0;
}
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #1e9421 } p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #1e9421; min-height: 21.0px } p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px "PingFang SC"; color: #1e9421 } p.p4 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #822d0f } p.p5 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #c81b13 } p.p6 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #c42275 } p.p7 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #000000 } p.p8 { margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Menlo; color: #000000; min-height: 21.0px } span.s1 { } span.s2 { font: 18.0px Menlo } span.s3 { color: #c81b13 } span.s4 { color: #822d0f } span.s5 { color: #000000 } span.s6 { color: #703daa } span.s7 { color: #0435ff } span.s8 { color: #c42275 } span.s9 { color: #539aa4 } span.s10 { font: 18.0px "PingFang SC" } span.s11 { color: #1e9421 } span.s12 { font: 18.0px "PingFang SC"; color: #1e9421 } span.s13 { color: #78492a } span.s14 { color: #3e1e81 }</style>
POJ 3251 Big Square