UVALive 2517 Moving Object Recognition(模拟)

  题目看上去很吓人,很高端,但其实很简单,不要被吓到,照搬题目的公式就可以了。

  方法:用BFS求出最大块和重心,找出题目公式需要的未知量,然后套到题目公式里就可以求出答案了。

  代码:

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 550
int n,m,go[][] = {{,},{-,},{,},{,-}};
int vis[N][N],Max;
char maps[N][N],op[N];
double X[N*],Y[N*];
struct Pos
{
int x,y;
};
bool in_maps(int x,int y)
{
return (x>= && x <= n && y>= && y<=m);
}
int bfs(int sx,int sy)
{
queue<Pos> que;
while(!que.empty()) que.pop();
Pos now,nxt;
now.x = sx; now.y = sy;
que.push(now);
int tot = ;
vis[sx][sy] = ;
while(!que.empty())
{
now = que.front();
que.pop();
tot++;
for(int i = ; i < ; i++)
{
nxt.x = now.x + go[i][];
nxt.y = now.y + go[i][];
if(in_maps(nxt.x,nxt.y) && !vis[nxt.x][nxt.y] && maps[nxt.x][nxt.y]=='x')
{
que.push(nxt);
vis[nxt.x][nxt.y] = ;
}
}
}
return tot;
}
void get_Max()
{
int nxtx,nxty,tmp,startx,starty;
Max = -;
memset(vis,,sizeof(vis));
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
if(maps[i][j] == 'x' && !vis[i][j])
{
tmp = bfs(i,j);
if(tmp > Max)
{
Max = tmp;
startx = i;
starty = j;
}
}
}
}
// printf("Max = %d\n",Max);
// printf("sx = %d sy = %d\n",startx,starty);
memset(vis,,sizeof(vis));
bfs(startx,starty);
}
void get_xy(int k)
{
double sumx = ,sumy = ;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
if(vis[i][j])
{
sumy += (j*1.0);
sumx += (i*1.0);
}
}
}
sumx /= Max;
sumy /= Max;
X[k] = sumx;
Y[k] = sumy;
}
int main()
{
int T;
double ansx,ansy;
while(~scanf("%d%d",&m,&n))
{
if(n+m==) break;
T = ;
while()
{
for(int i = ; i <= n; i++)
{
scanf("%s",maps[i]+);
}
scanf("%s",op);
get_Max();
get_xy(T);
T++;
if(op[]=='=') break;
}
//printf("T = %d\n",T);
T /= ;
ansx = ansy = 0.0;
for(int i = ; i < T; i++)
{
ansx += (X[i+T] - X[i]);
ansy += (Y[i+T] - Y[i]);
}
ansx /= (T*T);
ansy /= (T*T);
printf("%.2lf %.2lf\n",ansy,ansx);
}
return ;
}
上一篇:Intellij Idea修改css文件即时更新生成效果


下一篇:JS获取request字符串