时间：2007-10-02 成绩：1417.24 (240.17/300 + 464.20/500 + 516.46/900) 排名：10/565 第一名成绩：1776.68
代码： 300
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
class PirateTreasure{
public:
double getDistance(vector <int> steps, vector <string> directions){
int n = steps.size();
int x[2] = {0, 0}, y[2] = {0, 0};
for (int i = 0; i < n; i ++){
if (directions[i] == "NORTH"){
y[0] -= steps[i];
} else if (directions[i] == "SOUTH"){
y[0] += steps[i];
} else if (directions[i] == "EAST"){
x[0] += steps[i];
} else if (directions[i] == "WEST"){
x[0] -= steps[i];
} else if (directions[i] == "NORTHEAST"){
x[1] += steps[i];
y[1] -= steps[i];
} else if (directions[i] == "NORTHWEST"){
x[1] -= steps[i];
y[1] -= steps[i];
} else if (directions[i] == "SOUTHEAST"){
x[1] += steps[i];
y[1] += steps[i];
} else {
x[1] -= steps[i];
y[1] += steps[i];
}
}
double xx = (double)x[0] + (double)x[1] * sqrt(2) / 2.0;
double yy = (double)y[0] + (double)y[1] * sqrt(2) / 2.0;
return sqrt(xx * xx + yy * yy);
}
};
500
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class TurningLightOn{
public:
int minFlips(vector <string> board){
int c = board.size(), r = board[0].size();
int ret = 0;
for (int i = c - 1; i >= 0; i --){
for (int j = r - 1; j >= 0; j --){
if (board[i][j] == '0'){
ret ++;
for (int k = i; k >= 0; k --){
for (int l = j; l >= 0; l --){
if (board[k][l] == '0') board[k][l] = '1';
else board[k][l] = '0';
}
}
}
}
}
return ret;
}
};
900
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int const dir_x[4] = {0, 1, 0, -1};
int const dir_y[4] = {-1, 0, 1, 0};
int max_way[100][100];
int queue[10000][2];
bool vis[100][100];
class JumpingBoard{
public:
int maxJumps(vector <string> board){
int ret = -1;
int r = board.size(), c = board[0].size();
memset(max_way, 0, sizeof(max_way));
memset(vis, false, sizeof(vis));
int tail = 0;
vis[0][0] = true;
queue[0][0] = queue[0][1] = 0;
for (int head = 0; head <= tail; head ++){
int x = queue[head][0], y = queue[head][1];
for (int i = 0; i < 4; i ++){
int nx = x + dir_x[i] * (board[x][y] - '0');
int ny = y + dir_y[i] * (board[x][y] - '0');
if (nx >= 0 && nx < r && ny >= 0 && ny <= c && board[nx][ny] != 'H' && !vis[nx][ny]){
tail ++;
vis[nx][ny] = true;
queue[tail][0] = nx;
queue[tail][1] = ny;
}
}
}
for (int i = 0; i < r; i ++){
for (int j = 0; j < c; j ++) max_way[i][j] = -2147483647;
}
max_way[0][0] = 0;
for (int i = 0; i <= r * c * 2; i ++){
for (int j = 0; j < r; j ++){
for (int k = 0; k < c; k ++){
if (board[j][k] == 'H') continue;
for (int l = 0; l < 4; l ++){
int nx = j + dir_x[l] * (board[j][k] - '0');
int ny = k + dir_y[l] * (board[j][k] - '0');
if (nx >= 0 && nx < r && ny >= 0 && ny <= c && board[nx][ny] != 'H'){
max_way[nx][ny] = max(max_way[nx][ny], max_way[j][k] + 1);
}
}
}
}
}
for (int i = 0; i < r; i ++){
for (int j = 0; j < c; j ++){
if (!vis[i][j] || board[i][j] == 'H') continue;
for (int k = 0; k < 4; k ++){
int nx = i + dir_x[k] * (board[i][j] - '0');
int ny = j + dir_y[k] * (board[i][j] - '0');
if (nx >= 0 && nx < r && ny >= 0 && ny <= c && max_way[i][j] > max_way[nx][ny] && board[nx][ny] != 'H'){
return -1;
}
}
}
}
for (int i = 0; i < r; i ++){
for (int j = 0; j < c; j ++){
if (vis[i][j]) ret = max(ret, max_way[i][j]);
}
}
return ret + 1;
}
};