Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

深搜141ms水过,这题開5000ms是拿来吓唬人的麽

Posted by KatrineYang at 2016-09-14 13:15:27 on Problem 1327
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator