Fantasy's World

世界的小世界,我的大世界^_^

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  6 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

Problem Statement

You are given a String[] cityMap representing the layout of a city. The city consists of blocks. The first element of cityMap represents the first row of blocks, etc. A 'B' character indicates a location where there is a bus stop. There will be exactly one 'X' character, indicating your location. All other characters will be '.'. You are also given an int walkingDistance, which is the maximum distance you are willing to walk to a bus stop. The distance should be calculated as the number of blocks vertically plus the number of blocks horizontally. Return the number of bus stops that are within walking distance of your current location.

Definition

Class:BusStops
Method:countStops
Parameters:String[], int
Returns:int
Method signature:int countStops(String[] cityMap, int walkingDistance)
(be sure your method is public)

Constraints

-cityMap will contain between 1 and 50 elements, inclusive.
-Each element of cityMap will contain between 1 and 50 characters, inclusive.
-Each element of cityMap will contain the same number of characters.
-Each character of each element of cityMap will be 'B', 'X', or '.'.
-There will be exactly one 'X' character in cityMap.
-walkingDistance will be between 1 and 100, inclusive.

Examples

0)

{"...B.",
 ".....",
 "..X.B",
 ".....",
 "B...."}
3
Returns: 2
You can reach the bus stop at the top (3 units away), or on the right (2 units away). The one in the lower left is 4 units away, which is too far.

1)

{"B.B..",
 ".....",
 "B....",
 ".....",
 "....X"}
8
Returns: 3
A distance of 8 can get us anywhere on the map, so we can reach all 3 bus stops.

2)

{"BBBBB",
 "BB.BB",
 "B.X.B",
 "BB.BB",
 "BBBBB"}
1
Returns: 0
Plenty of bus stops, but unfortunately we cannot reach any of them.

3)

{"B..B..",
 ".B...B",
 "..B...",
 "..B.X.",
 "B.B.B.",
 ".B.B.B"}
3
Returns: 7


说实话我觉得这一题没啥意思,超简单,首先先确定X的位置,再用遍历数组找B的位置,再求相减的绝对值然后判断是否超出给出的最大距离就行了。相对这题PlayCars却很有意思,到现在我也没想出除了穷举以外的一个更好的算法,因为我觉得穷举可能会超时。有哪位有其它的办法的话,请告诉我,大家探讨一下,谢谢。好了,不废话了,下面是这题的答案:

public class BusStops {
 public static void main(String[] arg){
  BusStops total = new BusStops();
  
    System.out.println(total.countStops({"...B.",".....","..X.B",".....","B...."},3));
 }
 
 public int countStops(String[] cityMap, int walkingDistance){
  int sum= 0;
  int locationX = -1;
  int locationY = -1;
  for(int i=0;i<cityMap.length;i++){
   for(int j=0;j<cityMap[i].length();j++){
    if(cityMap[i].charAt(j)=='X'){
     locationX = i;
     locationY = j;
    }
   }
  }
  for(int i=0;i<cityMap.length;i++){
   for(int j=0;j<cityMap[i].length();j++){
    if(cityMap[i].charAt(j)=='B' && (Math.abs(locationX - i) + Math.abs(locationY - j)<=walkingDistance))
     sum++;
   }
  }
  return sum;
 }
}
posted on 2005-12-21 18:24 FinalFantasy 阅读(639) 评论(1)  编辑  收藏 所属分类: 读书笔记

Feedback

# re: Google编程挑战赛入围赛250分题及答案——BusStops题 2005-12-22 14:53 dotNet的程序员
用栈改进一下。
public class BusStops
{

public static void Main()
{
BusStops total = new BusStops();
//System.out.println(total.countStops({"...B.",".....","..X.B",".....","B...."},3));
System.Console.WriteLine(total.countStops(new string[]{"...B.",".....","..X.B",".....","B...."},3));
System.Console.ReadLine();
}

public int countStops(string[] cityMap, int walkingDistance)
{
Position xPosition=null;
System.Collections.Stack stack=new System.Collections.Stack();
for(int i=0;i<cityMap.Length;i++)
{
for(int j=0;j<cityMap[i].Length;j++)
{
if(cityMap[i][j]=='X')
{
xPosition=new Position();
xPosition.x = i;
xPosition.y = j;
}
else if(cityMap[i][j]=='B')
{
Position busStop=new Position();
busStop.x=i;
busStop.y=j;
stack.Push(busStop);
}
}
}
if (xPosition==null) throw new Exception("未发现X点");
if (stack.Count==0) return 0;
int sum= 0;
while (stack.Count>0)
{
Position busStop=(Position)stack.Pop();
if (Math.Abs(busStop.x-xPosition.x)+Math.Abs(busStop.y-xPosition.y)<=walkingDistance)
sum++;
}
return sum;
}

public class Position
{
public int x=0;
public int y=0;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: