emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
NewStation(入围赛750分真题)


Problem Statement
????
You are given a String[], grid, representing a city where each character in grid is a single city block. Each block will contain a digit representing the relative population on that block. For example, a block containing the digit '6' will contain three times as many people as a block containing the digit '2'. You are also given a String[], stations, containing the locations of all the fire stations within the city. Each element of stations is formatted as "r c" (quotes for clarity only), where r and c represent the row and column, respectively, of the block on which a fire station is located. Character j of element i of grid represents the block at row i, column j. All indices are 0-based.

The city has received enough funds to build one additional fire station, and the mayor has decided that it is most important to minimize the average distance between a person and the closest fire station to that person. The metric used to determine the distance between two locations in the city is the Manhattan distance between the two blocks on which the locations are situated. The Manhattan distance between two blocks (r1, c1) and (r2, c2) is |r1-r2|+|c1-c2| (the vertical bars represent absolute value). Determine the block on which the new station should be built and return its row and column formatted as "r c" (quotes for clarity only). The return String should contain no extra leading zeros. If multiple blocks are equally optimal, return the one with the lowest row, and if multiple optimal blocks have the same lowest row, return the one among them with the lowest column. If adding an additional fire station would not reduce the average distance between a person and the closest fire station to that person, return the empty String ("").
Definition
????
Class:
NewStation
Method:
location
Parameters:
String[], String[]
Returns:
String
Method signature:
String location(String[] grid, String[] stations)
(be sure your method is public)
????

Constraints
-
grid will contain between 1 and 20 elements, inclusive.
-
Each element of grid will contain between 1 and 20 characters, inclusive.
-
Each element of grid will contain exactly the same number of characters.
-
Each element of grid will contain only digits ('0'-'9').
-
At least one character in grid will be non-zero.
-
stations will contain between 1 and 10 elements, inclusive.
-
Each element of stations will be formatted as "r c" (quotes for clarity only), where r and c are each integers between 0 and 19, inclusive, with no leading zeros.
-
Each element of stations will represent a location within the boundaries of grid.
Examples
0)

????
{"111",
 "111",
 "111"}
{"1 1"}
Returns: "0 1"
There's an existing station at (1, 1) and each block contains exactly the same number of people. Placing a new station at either (0, 1), (1, 0), (1, 2), or (2, 1) would minimize the average distance. (0, 1) is chosen since it has the lowest row. Adding the new station reduces the average distance from approximately 1.33 to 1.0. The distance from each block to the nearest station becomes:
101
101
212
1)

????
{"111",
 "111",
 "111"}
{"0 0", "0 1", "0 2",
 "1 0", "1 1", "1 2",
 "2 0", "2 1", "2 2"}
Returns: ""
There's a fire station on every block, so adding a new station would not reduce the average distance.
2)

????
{"2312",
 "0233"}
{"1 3"}
Returns: "0 1"
Placing a fire station at (0, 1) would make the average distance 0.625.
3)

????
{"2312",
 "0233"}
{"1 1", "1 1"}
Returns: "0 3"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-08-23 16:37 emu 阅读(1660) 评论(4)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# emu的解法 2005-08-23 16:47 emu
public class NewStation {
    public static void main(String[] args) {
        NewStation ns = new NewStation(); ;
        String[] grid = {"2312",
 "0233"};
        String[] stations = {"1 1", "1 1"};
        System.out.println(ns.location(grid, stations));
    }

    public String location(String[] grid, String[] stations) {
        int[][] iGrid = new int[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            String s = grid[i];
            for (int j = 0; j < s.length(); j++) {
                iGrid[i][j] = s.charAt(j) - 48;
            }
        }
        boolean[][] iStations = new boolean[iGrid.length][iGrid[0].length];
        for (int i = 0; i < stations.length; i++) {
            String[] s = stations[i].split(" ");
            iStations[Integer.parseInt(s[0], 10)][Integer.parseInt(s[1], 10)] = true;
        }
        int minDistanceCount = count(iGrid, iStations);
        String result = "";
        for (int x = 0; x < iGrid.length; x++)
            for (int y = 0; y < iGrid[0].length; y++) {
                int c = count(iGrid, iStations, x, y);
                if (c < minDistanceCount) {
                    result = x + " " + y;
                   minDistanceCount = c;
                }
            }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations) {
        int result = 0;
        for (int i = 0; i < iGrid.length; i++)
            for (int j = 0; j < iGrid[0].length; j++)
                if (!iStations[i][j] && iGrid[i][j] > 0) {
                    int minCount = 99999;
                    for (int x = 0; x < iGrid.length; x++)
                        for (int y = 0; y < iGrid[0].length; y++)
                            if (iStations[x][y] &&
                                (Math.abs(x - i) + Math.abs(y - j) * iGrid[i][j]) <
                                minCount)
                                minCount = Math.abs(x - i) +
                                           Math.abs(y - j) * iGrid[i][j];
                    result += minCount;
                }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations, int x, int y) {
        boolean[][] tmpStations  = new boolean[iStations.length][iStations[0].length];
        for (int i=0;i<iStations.length;i++)
            for (int j=0;j<iStations[0].length;j++)
                tmpStations[i][j]=(x==i&&y==j)?(true):(iStations[i][j]);
        return count(iGrid, tmpStations);

    }

}

  回复  更多评论
  

# re: NewStation(入围赛750分真题) 2005-08-25 11:01 emu
遗憾的很，我这个答案没有通过google的系统测试。  回复  更多评论
  

# drekar的解法 2005-12-09 12:58 drekar
穷举：

public class NewStation {

　int MaxRow;
　int MaxCol;
　int NumOfExistedStation;
　int[][] gridMap;
　boolean[][] stationMap;
　int[][] fireStations;

　/**
　 * Find the location for new station.
　 *
　 * @param grid
　 *　　　　　　population for city's each block
　 * @param stations
　 *　　　　　　existed fire stations' coordinate
　 * @return the best location of new station
　 *
　 */
　public String location(String[] grid, String[] stations) {
　　MaxRow = grid.length;
　　MaxCol = grid[0].length();
　　NumOfExistedStation = stations.length;

　　// get grid population map
　　gridMap = new int[MaxRow][MaxCol];
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++)
　　　　gridMap[i][j] = grid[i].charAt(j) - '0';

　　// get fire station map
　　stationMap = new boolean[MaxRow][MaxCol];
　　fireStations = new int[NumOfExistedStation + 1][2]; // [][0] for 'row', [][1] for 'column'
　　for (int i = 0; i < NumOfExistedStation; i++) {
　　　String[] temp = stations[i].split(" ");
　　　fireStations[i][0] = Integer.parseInt(temp[0]); // station(#i)'s row
　　　fireStations[i][1] = Integer.parseInt(temp[1]); // station(#i)'s column
　　　stationMap[fireStations[i][0]][fireStations[i][1]] = true; // mark it as a station on the map
　　}

　　int minTotalDistance = Integer.MAX_VALUE;
　　int bestRow = -1;
　　int bestCol = -1;
　　// search for best new station location
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++) {
　　　　if (stationMap[i][j])
　　　　　continue;

　　　　// this location has no station, try to set new station here
　　　　fireStations[NumOfExistedStation][0] = i;
　　　　fireStations[NumOfExistedStation][1] = j;

　　　　int newTotalDistance = calculateTotalDistance();
　　　　if (minTotalDistance > newTotalDistance) {
　　　　　// found a better location
　　　　　minTotalDistance = newTotalDistance;
　　　　　bestRow = i;
　　　　　bestCol = j;
　　　　}
　　　}

　　if (bestRow == -1)
　　　return "";
　　return bestRow + " " + bestCol;
　}

　/**
　 * @return total distance if using selected new location
　 */
　public int calculateTotalDistance() {
　　int distance = 0;
　　for (int i = 0; i < MaxRow; i++)
　　　for (int j = 0; j < MaxCol; j++)
　　　　distance += distanceToNearestStation(i, j) * gridMap[i][j];
　　return distance;
　}

　/**
　 * @param row
　 *　　　　　　row of current location
　 * @param col
　 *　　　　　　column of current location
　 * @return distance to the nearest station from location 'row col'
　 */
　public int distanceToNearestStation(int row, int col) {
　　int distance = Integer.MAX_VALUE;
　　for (int i = 0; i < NumOfExistedStation + 1; i++) {
　　　int tempDistance = Math.abs(row - fireStations[i][0])
　　　　　+ Math.abs(col - fireStations[i][1]);
　　　if (distance > tempDistance) {
　　　　distance = tempDistance;
　　　　if (distance == 0)
　　　　　break;
　　　}
　　}
　　return distance;
　}

　/**
　 * 主程序入口
　 *
　 * @param args
　 */
　public static void main(String[] args) {
　　NewStation ns = new NewStation();
　　String[] grid = { "2312", "0233" };
　　String[] stations = { "1 1", "1 1" };

　　String result = ns.location(grid, stations);
　　System.out.println(result);
　}
}
  回复  更多评论
  

# re: NewStation(入围赛750分真题) 2005-12-13 12:10 titian2046
#include <string>
#include <vector>
#include <list>
#include <map>

#include "math.h"
using namespace std;

#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a


#define MAXN 4
#define maxnum 9999999
#define minnum 0.0000001
#define abs(a) ((a>0)?(a):(-1*(a)))
#define eq(a,b) (abs((a)-(b))<minnum)



using namespace std;
#define abs(a) ((a>0)?(a):(-1*(a)))

class NewStation
{
public:
int sts[20][20];
string ret;
vector<string> mgrid;
string location(vector <string> grid, vector <string> stations)
{

mgrid = grid;
int i,j,r=-1,c=0;

init(stations);
long mindist = alldis();
long k;


for (i=0;i<20;i++)
{
for (j=0;j<20;j++)
{
if (sts[i][j]!=1)
{
sts[i][j] =1;
k = alldis();
if ( mindist>k)
{
mindist = k;
r = i;
c = j;
}
sts[i][j] =0;
}
}
}
if (r==-1)
{
return "";
}
else
{
char s1[20];
sprintf(s1,"%d %d",r,c);
ret.assign(s1);
return ret;
}
};
void init(vector <string> stations)
{
int r,c;
int i;
for (i=0;i<20;i++)
{
for (int j=0;j<20;j++)
sts[i][j] = 0;
}
for (i=0;i<stations.size();i++)
{
sscanf(stations[i].c_str(),"%d %d",&r,&c);
sts[r][c] = 1;
}
}
long alldis()
{
long lret =0,lmin;
int i,j,i1,j1;
int len = strlen(mgrid[0].c_str());
for (i=0;i<mgrid.size();i++)
{
for (j =0;j<len;j++)
{
lmin = 100;
for (i1=0;i1<mgrid.size();i1++)
{
for (j1 =0;j1<len;j1++)
{
if (sts[i1][j1]==1&& (abs(i1-i)+abs(j1-j))<lmin)
{
lmin = (abs(i1-i)+abs(j1-j));
}
}
}
lret+= (mgrid[i][j]-'0')*lmin;
}
}
return lret;
};
};
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: