| ||||||||||
| 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 | |||||||||
这题也会TLE?最暴力的都AC了(附代妈)//============================================================================
// Name : main1027.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <string>
#include <iostream>
using namespace std;
//int cnt;
int maxi;
int getCnt(int colour[][15], int rep[][15], int cnt[][15], int x, int y, bool isFirst){
//if(rep[x][y] != -1) return cnt[x][y];
int count = 1;
if(isFirst) rep[x][y] = 10*y+x;
int col = colour[x][y];
if(y+1 < 15 && rep[x][y+1] == -1 && colour[x][y+1] == col){
rep[x][y+1] = rep[x][y];
count += getCnt(colour, rep, cnt, x, y+1, false);
}
if(x+1 < 10 && rep[x+1][y] == -1 && colour[x+1][y] == col){
rep[x+1][y] = rep[x][y];
count += getCnt(colour, rep, cnt, x+1, y, false);
}
if(x>0 && rep[x-1][y] == -1 && colour[x-1][y] == col){
rep[x-1][y] = rep[x][y];
count += getCnt(colour, rep, cnt, x-1, y, false);
}
if(y>0 && rep[x][y-1] == -1 && colour[x][y-1] == col){
rep[x][y-1] = rep[x][y];
count += getCnt(colour, rep, cnt, x, y-1, false);
}
cnt[x][y] = count;
return count;
}
void getRep(int colour[][15], int rep[][15], int cnt[][15]){
maxi = 0;
for(int j = 0; j < 15; j++){
for(int i = 0; i < 10; i++){
if(rep[i][j] != -1 || colour[i][j] == 0) continue;
//rep[i][j] = 10*j+i;
int temp = getCnt(colour, rep, cnt, i, j, true);
if(temp > maxi) maxi = temp;
}
}
}
int main() {
int cases;
cin >> cases;
for(int ii = 0; ii < cases; ii++){
cout << "Game " << (ii+1) << ":" << endl << endl;
int colour[10][15] = {0};
for(int i = 0; i < 10; i++){
string s;
cin >> s;
for(int j = 0; j < 15; j++){
colour[9-i][j] = (int)s[j];
}
}
int round = 0;
int remain = 10 * 15;
int score = 0;
while(1){
round++;
int rep[10][15];
int cnt[10][15] = {0};
for(int i = 0; i < 10; i++){
for(int j = 0; j < 15; j++){
rep[i][j] = -1;
}
}
getRep(colour, rep, cnt);
int tar, ii, jj;
for(int k = 0; k < 150; k++){
ii = k%10;
jj = k/10;
if(cnt[ii][jj] == maxi){
tar = k;
break;
}
}
if(maxi <= 1) break;
//round++;
remain -= maxi;
score += (maxi-2)*(maxi-2);
cout << "Move " << round << " at (" << ii+1 << "," << jj+1 << "): removed " << maxi << " balls of color " << (char)colour[ii][jj] << ", got " << (maxi-2)*(maxi-2) << " points." << endl;
//Move 1 at (4,1): removed 32 balls of color B, got 900 points.
for(int i = 0; i < 10; i++){
for(int j = 0; j < 15; j++){
if(rep[i][j] == tar){
colour[i][j] = 0;
}
}
}
for(int j = 0; j < 15; j++){
int yuan = 0, xian = 0;
while(1){
while(yuan < 10 && colour[yuan][j] == 0){
yuan++;
}
if(yuan == 10)break;
colour[xian][j] = colour[yuan][j];
xian++;
yuan++;
}
//if(yuan == 10){
for(int q = xian; q < 10; q++) colour[q][j] = 0;
//}
}
int Xi = 0, Yu = 0;
while(1){
while(Yu < 15 && colour[0][Yu] == 0){
Yu ++;
}
if(Yu == 15) break;
for(int i = 0; i < 10; i++){
colour[i][Xi] = colour[i][Yu];
}
Xi++;
Yu++;
}
for(int q = Xi; q < 15; q++){
for(int i = 0; i < 10; i++){
colour[i][q] = 0;
}
}
/*
for(int i = 0; i < 10; i ++){
for(int j = 0; j < 15; j ++){
cout << rep[9-i][j] << " ";
}
cout << endl;
}
for(int i = 0; i < 10; i ++){
for(int j = 0; j < 15; j ++){
cout << cnt[9-i][j] << " ";
}
cout << endl;
}
cout << maxi << endl;*/
}
if(remain == 0) score += 1000;
cout << "Final score: " << score << ", with " << remain << " balls remaining." << endl << endl;
//Final score: 3661, with 1 balls remaining.
}
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator