Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求助,我自己的算法,两次判断的想法,应该没错误的事情是这样的,我先判断所有竖线的总和是否等于高度两倍,在判断所有横线总和是否等于宽度两倍,如果满足继续判断,有没有可以不碰壁直接从最左到最右,不碰壁从最下到最上的情况,如果满足,就是possible,否则就是impossible,感觉没错,以下是我的代码,求大神指点,ORZimport java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanner; public class Main { public static int count = 0; public static int maxwidth = 0; public static int minwidth = 0; public static int maxheight = 0; public static int minheight = 0; public static boolean maxheight(ArrayList a) { int x = 0; int y = 0; int height = 0; int maxx1 = 0; int maxx2 = 0; int minX1 = 0; int minX2 = 0; int maxheight = 0; int I = 0; int K = 0; boolean getaccess = false ; for (int i = 0; i < a.size() / 2; i++) { String str = a.get(i).toString(); String[] strgroup = str.split(" "); x = Integer.parseInt(strgroup[0]); y = Integer.parseInt(strgroup[1]); for(int k=i + a.size()/2; k<a.size(); k++ ) { String str2 = a.get(k).toString(); String[] strgroup2 = str.split(" "); int X = Integer.parseInt(strgroup[0]); int Y = Integer.parseInt(strgroup[1]); height = Math.abs(Y - y); if(height > maxheight) { maxheight = height; I = i; K = k; } } } maxx1 = Integer.parseInt(a.get(I).toString().split(" ")[0]); maxx2 = Integer.parseInt(a.get(I + 1).toString().split(" ")[0]); minX1 = Integer.parseInt(a.get(K + 1).toString().split(" ")[0]); minX2 = Integer.parseInt(a.get(K).toString().split(" ")[0]); if(maxx1 > minX2 || maxx2 < minX1) { getaccess = false; }else { getaccess = true; } return getaccess; } public static boolean maxwidth(ArrayList a) { int x = 0; int y = 0; int width = 0; int maxy1 = 0; int maxy2 = 0; int minY1 = 0; int minY2 = 0; int maxwidth = 0; int I = 0; int K = 0; boolean getaccess = false ; for (int i = 0; i < a.size() / 2; i++) { String str = a.get(i).toString(); String[] strgroup = str.split(" "); x = Integer.parseInt(strgroup[0]); y = Integer.parseInt(strgroup[1]); for(int k=i + a.size()/2; k<a.size(); k++ ) { String str2 = a.get(k).toString(); String[] strgroup2 = str.split(" "); int X = Integer.parseInt(strgroup[0]); int Y = Integer.parseInt(strgroup[1]); width = Math.abs(X - x); if(width > maxwidth) { maxwidth = width; I = i; K = k; } } } maxy1 = Integer.parseInt(a.get(I).toString().split(" ")[1]); maxy2 = Integer.parseInt(a.get(I + 1).toString().split(" ")[1]); minY1 = Integer.parseInt(a.get(K + 1).toString().split(" ")[1]); minY2 = Integer.parseInt(a.get(K).toString().split(" ")[1]); if(maxy1 > minY2 || maxy2 < minY1) { getaccess = false; }else { getaccess = true; } return getaccess; } public static int getheight(ArrayList a) { int height = 0; ArrayList str1 = new ArrayList(); ArrayList str2 = new ArrayList(); for (int i = 0; i < a.size(); i++) { String str = a.get(i).toString(); String[] strgroup = str.split(" "); str2.add(strgroup[1]); String s = str2.get(i).toString(); int c = Integer.parseInt(s); if (c - maxheight > 0) { maxheight = c; } } for (int i = 0; i < a.size(); i++) { String s = str2.get(i).toString(); int c = Integer.parseInt(s); if (c - minheight < 0) { minheight = c; } } height = maxheight - minheight; return height; } public static int getwidth(ArrayList b) { int width = 0; ArrayList str1 = new ArrayList(); ArrayList str2 = new ArrayList(); for (int i = 0; i < b.size(); i++) { String str = b.get(i).toString(); String[] strgroup = str.split(" "); str2.add(strgroup[0]); String s = str2.get(i).toString(); int c = Integer.parseInt(s); if (c - maxwidth > 0) { maxwidth = c; } } for (int i = 0; i < b.size(); i++) { String s = str2.get(i).toString(); int c = Integer.parseInt(s); if (c - minwidth < 0) { minwidth = c; } } width = maxwidth - minwidth; return width; } public static void mysubtraction(Object object, Object object2, ArrayList<Integer> a, ArrayList<Integer> b) { String str1 = object.toString(); String str2 = object2.toString(); if (str1.charAt(0) - str2.charAt(0) == 0) { b.add(Math.abs(str1.charAt(2) - str2.charAt(2))); } else if (str1.charAt(2) - str2.charAt(2) == 0) { a.add(Math.abs(str1.charAt(0) - str2.charAt(0))); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); while (Integer.parseInt(str) != 0) { String strr = sc.nextLine(); ArrayList num = new ArrayList(); if (str.split(" ").length == 1) { count++; } while (strr.length() != 1) { num.add(strr); strr = sc.nextLine(); } ArrayList<Integer> leftright = new ArrayList<Integer>(); ArrayList<Integer> updown = new ArrayList<Integer>(); for (int k = 0; k < num.size(); k++) { if (k < num.size() - 1) { mysubtraction(num.get(k + 1), num.get(k), leftright, updown); } else { mysubtraction(num.get(num.size() - 1), num.get(0), leftright, updown); } } int leftrightsum = 0; int updownsum = 0; for (int k = 0; k < leftright.size(); k++) { leftrightsum = leftrightsum + leftright.get(k); } for (int k = 0; k < updown.size(); k++) { updownsum = updownsum + updown.get(k); } int width = getwidth(num); int height = getheight(num); if (leftrightsum == 2 * width && updownsum == 2 * height) { if (maxwidth(num) == true && maxheight(num) == true) { System.out.println("Floor #" + count); System.out.println("Surveillance is possible."); } else { System.out.println("Floor #" + count); System.out.println("Surveillance is impossible."); } } else { System.out.println("Floor #" + count); System.out.println("Surveillance is impossible."); } str = strr; } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator