| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
深搜141ms水过,这题開5000ms是拿来吓唬人的麽#include <iostream>
#include <stdio.h>
using namespace std;
int m,k;
bool mp[260][260];
int x, y;
double aveX, aveY;
double X[260], Y[260];
int T, N, cnt;
int keyong;
void dfs(int i, int j, bool used[260][260]){
used[i][j] = 1;
cnt++;
x += i, y += j;
if(i>0 && !used[i-1][j] && mp[i-1][j]) dfs(i-1, j, used);
if(i<k-1 && !used[i+1][j] && mp[i+1][j]) dfs(i+1, j, used);
if(j>0 && !used[i][j-1] && mp[i][j-1]) dfs(i, j-1, used);
if(j<m-1 && !used[i][j+1] && mp[i][j+1]) dfs(i, j+1, used);
}
void jisuan(){
bool used[260][260] = {0};
int yiyong = 0, mx = 0;
for(int i = 0; i < k; i++){
for(int j = 0; j < m; j++){
if(keyong - yiyong <= mx) break;
if(used[i][j] || !mp[i][j]) continue;
x = 0, y = 0;
cnt = 0;
dfs(i,j,used);
yiyong += cnt;
if(cnt > mx){
mx = cnt;
aveX = x*1.0/cnt;
aveY = y*1.0/cnt;
}
}
}
X[N] = aveX, Y[N] = aveY;
}
int main() {
while(1){
scanf("%d%d", &m, &k);
if(m+k==0) break;
N = 0;
while(1){
keyong = 0;
for(int i = 0; i < k; i++){
char temp[260];
scanf("%s", temp);
for(int j = 0; j < m; j++){
if(temp[j] == 'x') {
mp[i][j] = 1;
keyong++;
}
else mp[i][j] = 0;
}
}
jisuan();
//cout << X[N] << " " << Y[N] << endl;
N++;
char fei[260];
scanf("%s", fei);
if(fei[0] == '=') break;
}
T = N/2;
double resX = 0, resY = 0;
for(int i = 0; i < T; i++){
resX += X[T+i] - X[i];
resY += Y[T+i] - Y[i];
}
double sqT = (double) T*T;
resX /= sqT;
resY /= sqT;
printf("%.2lf %.2lf\n", resY, resX);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator