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