emu in blogjava

:: 管理 ::

171 隨筆 :: 103 文章 :: 1052 評論 :: 2 Trackbacks

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

{".........",
 "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.
..

{"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.

{".X..X.X.XX.",
 "..X..X...X.",
 "X......X..X",
 ".X....X...X",
 "..XXXX.X.X.",
 "XXX..XXX..X"}

{"0 0 0 0"}

Returns: {"." }

{".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 閱讀(1309) 評論(5) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

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));
}
}
回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Problem Statement

Definition

Constraints

Examples

評論