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

一次AC

Posted by KatrineYang at 2016-10-23 15:04:29 on Problem 1414
#include <iostream>
#include <stdio.h>
using namespace std;

int state[15][15];
int numb[15];
int n, c;
bool used[15][15];
int gs, gsZJ;

bool inRange(int x, int y){
	return x > 0 && x <= n && y > 0 && y <= x;
}

int dir[6][2] = {{-1,-1},{-1,0},{0,1},{1,1},{1,0},{0,-1}};
const int MN = -2147483648;

bool init(){
	scanf("%d%d", &n, &c);
	//printf("n=%d\n",n);
	if(n==0) return 0;
	for(int i = 0; i < 15; i++) {
		//printf("i=%d d", i);
		numb[i] = 0;
	}
	//printf("n=%d\n", n);
	for(int i = 1; i <= n; i++){
		//printf("i=%d\n", i);
		for(int j = 1; j <= i; j++){
			scanf("%d", &state[i][j]);
			//printf("%d %d %d\n", i,j,state[i][j]);
			numb[state[i][j]]++;
		}
	}
	return 1;
}

void search(int x, int y){
	if(used[x][y]) return;
	used[x][y] = 1;
	if(state[x][y] == c) gsZJ++;
	else gs++;
	for(int i = 0; i < 6; i++){
		int x1 = x + dir[i][0], y1 = y + dir[i][1];
		if(inRange(x1, y1) && (!state[x][y] || state[x][y] == state[x1][y1])) search(x1, y1);
	}
}

int getAns(){
	int ans = MN;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			if(state[i][j]) continue;
			state[i][j] = c;
			numb[c]++;
			gs = 0;
			gsZJ = 0;
			for(int k = 1; k <= n; k++){
				for(int l = 1; l <= k; l++){
					used[k][l] = 0;
				}
			}
			for(int k = 1; k <= n; k++){
				for(int l = 1; l <= k; l++){
					if(!state[k][l]) search(k,l);
				}
			}
			int tmp = (n*(n+1)/2-numb[c]-gs) - (numb[c]-gsZJ);
			if(tmp > ans) ans = tmp;
			state[i][j] = 0;
			numb[c]--;
		}
	}
	return ans;
}

int main() {
	while(init()){
		//cout << 1 << endl;
		printf("%d\n", getAns());
	}
	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