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

Problem Statement

     You are given a black and white image in a String[], image. Character j of element i (both 0-based indices) of image represents the pixel in row i, column j. 'X' characters represent black pixels and '.' characters represent white pixels. You are given a String[], crops, which contains a series of rectangular crop operations that are performed on the image. Cropping is an operation that trims an image so that only the specified area of the original image remains. Each element of crops is formatted as "r1 c1 r2 c2" (quotes for clarity only), where the upper left corner of the area to crop is at row r1, column c1, and the lower right corner is at row r2, column c2. The coordinates are inclusive. The crop operations are performed in the order that they appear in crops, and each one is performed on the most recent version of the image. The constraints will guarantee that all crop operations will be within the boundaries of the image. Return the final cropped image as a String[] in the same format as the original image String[].

Definition

    
Class: Crop
Method: crop
Parameters: String[], String[]
Returns: String[]
Method signature: String[] crop(String[] image, String[] crops)
(be sure your method is public)
    

Constraints

- image will contain between 1 and 50 elements, inclusive.
- Each element of image will contain between 1 and 50 characters, inclusive.
- Each element of image will contain exactly the same number of characters.
- Each element of image will contain only '.' and uppercase 'X' characters.
- crops will contain between 1 and 10 elements, inclusive.
- Each element of crops will be formatted as described in the problem statement and no integers within crops will contain extra leading zeros.
- Within each element of crops, r2 will be greater than or equal to r1 and c2 will be greater than or equal to c1.
- crops will contain no operations that exceed the boundaries of the image at any time in the cropping process.

Examples

0)
     
{".........",
 "X.XXXXXXX",
 "....X....",
 "........." }
{"1 0 2 8", "0 0 1 1"}
Returns: {"X.", ".." }
The first crop effectively removes the top and bottom rows of the image and results in: 

X.XXXXXXX
....X....

The second crop is then performed relative to the new image: 

X.
..
1)
     
{"X.X.X.X.X.X.X.X",
 ".X.X.X.X.X.X.X."}
{"0 0 1 14", "0 0 1 14", "0 0 1 14"}
Returns: {"X.X.X.X.X.X.X.X", ".X.X.X.X.X.X.X." }
These crops don't affect the original image at all.
2)
     
{".X..X.X.XX.",
 "..X..X...X.",
 "X......X..X",
 ".X....X...X",
 "..XXXX.X.X.",
 "XXX..XXX..X"}
{"0 0 0 0"}
Returns: {"." }
3)
     
{".X..X.X.XX.",
 "..X..X...X.",
 "X......X..X",
 ".X....X...X",
 "..XXXX.X.X.",
 "XXX..XXX..X"}
{"1 0 5 9", "0 1 4 8", "0 0 3 5"}
Returns: {".X..X.", "......", "X....X", ".XXXX." }

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-25 11:04 emu 阅读(1288) 评论(5)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: Crop(入围赛250分真题) 2005-09-29 19:22 huangyi
看来英文还得加强了 看了半天死活没看懂
感觉google的比赛 挺象acm的 又貌似比acm实用一点  回复  更多评论
  

# re: Crop(入围赛250分真题) 2005-12-06 15:12 Anson
把所以得r1,c1相加，得到 newr1，newc1，之后最后一项的r2，c2分别加上newr1,newc1,得到 newr2,newc2,
最后裁剪出矩形newr1,newc1,newr2,newc2.应该是这样，是个坐标转化问题.  回复  更多评论
  

# re: Crop(入围赛250分真题) 2005-12-09 15:40 drekar
Anson的分析正确。

下面是我的解：

public class Crop {

　public String[] crop(String[] image, String[] crops) {
　　int cropsTimes = crops.length;
　　if (cropsTimes == 0)
　　　return image;

　　int MaxRow = image.length;
　　int MaxCol = image[0].length();
　　
　　int x0 = 0;
　　int y0 = 0;
　　int x1 = MaxRow;
　　int y1 = MaxCol;
　　for (int i=0; i<cropsTimes; i++) {
　　　String[] temp = crops[i].split(" ");

　　　if (i == cropsTimes-1) {
　　　　x1 = x0 + Integer.parseInt(temp[2]);
　　　　y1 = y0 + Integer.parseInt(temp[3]);
　　　}
　　　x0 += Integer.parseInt(temp[0]);
　　　y0 += Integer.parseInt(temp[1]);
　　}
　　
　　String[] result = new String[x1-x0+1];
　　for (int i=x0; i<=x1; i++)
　　　result[i-x0] = image[i].substring(y0, y1+1);
　　　
　　return result;
　}

　public static void main(String[] args) {
　　String[] image = { ".X..X.X.XX.", "..X..X...X.", "X......X..X",
　　　　".X....X...X", "..XXXX.X.X.", "XXX..XXX..X" };
　　String[] crops = { "1 0 5 9", "0 1 4 8", "0 0 3 5" };
　　
　　Crop cp = new Crop();
　　
　　String[] result = cp.crop(image, crops);
　　
　　for (int i=0; i<result.length; i++)
　　　System.out.println(result[i]);

　}

}
  回复  更多评论
  

# re: Crop(入围赛250分真题) 2005-12-11 17:52 小飞侠
public class test {
public static String[] crop(String[] image, String[] crops) {
String[] result, crop;
int row0, row1, col0, col1, x0, y0, x1, y1, n, i;

row0 = col0 = 0;
row1 = image.length - 1;
col1 = image[0].length() - 1;
for (i = 0, n = crops.length; i < n; i++) {
crop = crops[i].split(" ");
x0 = Integer.parseInt(crop[0]);
y0 = Integer.parseInt(crop[1]);
x1 = Integer.parseInt(crop[2]);
y1 = Integer.parseInt(crop[3]);

//边界判断
if (x0 < 0 || x0 > x1 || x1 > row1)
continue;
if (y0 < 0 || y0 > y1 || y1 > col1)
continue;

row1 = row0 + x1;
col1 = col0 + y1;
row0 += x0;
col0 += y0;

}

//输出
result = new String[row1 - row0 + 1];
for (i = 0, n = result.length; i < n ; i++) {
result[i] = image[i+row0].substring(col0, col1+1);
}

for (i = 0, n = result.length; i < n ; i++) {
System.out.println(result[i]);
}
return result;
}

public static void main(String args[]) {
String[] image, crops, result;

image = new String[4];
crops = new String[2];

image[0] = new String("X.X.X.X.X.X.X.X");
image[1] = new String(".X.X.X.X.X.X.X.");
image[2] = new String(".X.X.X.X.X.X.X.");
image[3] = new String("X.X.X.X.X.X.X.X");


crops[0] = new String("1 1 2 3");
crops[1] = new String("0 0 1 1");

crop(image, crops);

}

}  回复  更多评论
  

# re: Crop(入围赛250分真题) 2005-12-12 11:35 emu
小飞侠的解法好。这是emu 的很笨的解法：
public class Crop
{
public String[] crop(String[] image, String[] crops) {
String crop = crops[0];
String[] t = crop.split(" ");
int r1= Integer.parseInt(t[0],10);
int c1= Integer.parseInt(t[1],10);
int r2= Integer.parseInt(t[2],10);
int c2= Integer.parseInt(t[3],10);
if(r2>(image.length-1)) r2=(image.length-1);
if(c2>(image[0].length()-1)) c2=(image[0].length()-1);
if( r1>0 || c1>0 || r2<(image.length-1) || c2<(image[0].length()-1) ){
String[] tmpImage = new String[r2-r1+1];
for(int i=r1;i<=r2;i++)
tmpImage[i-r1] = image[i].substring(c1,c2+1);
if(crops.length>1){
String[] tmpCrops = new String[crops.length-1];
for(int i=1;i<crops.length;i++) tmpCrops[i-1] = crops[i];
return crop(tmpImage,tmpCrops);
}else{
return tmpImage;
}
}else
return image;
}
public static void main(String[] args)
{
Crop c = new Crop();
String[] result = c.crop(
new String[]{".........","X.XXXXXXX","....X....","........."},
new String[]{"1 0 2 8", "0 0 1 1"}
);
System.out.println(java.util.Arrays.asList(result));

result = c.crop(
new String[]{"X.X.X.X.X.X.X.X", ".X.X.X.X.X.X.X."},
new String[]{"0 0 1 14", "0 0 1 14", "0 0 1 14"}
);
System.out.println(java.util.Arrays.asList(result));

result = c.crop(
new String[]{".X..X.X.XX.", "..X..X...X.", "X......X..X", ".X....X...X", "..XXXX.X.X.", "XXX..XXX..X"},
new String[]{"0 0 0 0"}
);
System.out.println(java.util.Arrays.asList(result));

result = c.crop(
new String[]{".X..X.X.XX.", "..X..X...X.", "X......X..X", ".X....X...X", "..XXXX.X.X.", "XXX..XXX..X"},
new String[]{"1 0 5 9", "0 1 4 8", "0 0 3 5"}
);
System.out.println(java.util.Arrays.asList(result));
}
}
  回复  更多评论
  


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