2688 Cleaning Robot

「2688 Cleaning Robot」の編集履歴(バックアップ)一覧はこちら

2688 Cleaning Robot」(2006/05/14 (日) 00:54:36) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2688 Cleaning Robot **解答例 import java.util.*; public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(true){ int w = sc.nextInt(); int h = sc.nextInt(); if(w==0&&h==0) break; char[][] floor = new char[h][w]; for(int i=0;i<h;i++){ String s = sc.next(); for(int j=0;j<w;j++){ floor[i][j] = s.charAt(j); } } Solver sol = new Solver(w, h, floor); System.out.println(sol.solve()); } } } class Solver{ int w; int h; char[][] floor; int size; // 1 + num of dirty tile Point loc[]; int[][] dist; int max; public Solver(int w, int h, char[][] floor) { this.w = w; this.h = h; this.floor = floor; // initialize information of robot and dirty tiles size = 1; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(floor[i][j]=='*'){ size++; } } } int cnt = 1; loc = new Point[size]; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(floor[i][j]=='o') loc[0] = new Point(i,j); if(floor[i][j]=='*'){ loc[cnt] = new Point(i,j); cnt++; } } } // initialize distance table initDist(); max = Integer.MAX_VALUE; } private void initDist() { dist = new int[size][size]; for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ char[][] f = new char[h][w]; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ f[y][x] = floor[y][x]; } } int sx = loc[i].x; int sy = loc[i].y; int ex = loc[j].x; int ey = loc[j].y; f[sx][sy] = '!'; int d = 0; while(true){ if(f[ex][ey]=='!') break; boolean end = true; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(f[y][x]!='x'&&f[y][x]!='!'){ if(y>0 &&f[y-1][x]=='!'){ f[y][x] = '?'; end = false;} if(y<h-1&&f[y+1][x]=='!'){ f[y][x] = '?'; end = false;} if(x>0 &&f[y][x-1]=='!'){ f[y][x] = '?'; end = false;} if(x<w-1&&f[y][x+1]=='!'){ f[y][x] = '?'; end = false;} } } } if(end){ d = -1; break; } else{ for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(f[y][x]=='?') f[y][x] = '!'; } } d++; } } dist[i][j] = d; // System.out.print(dist[i][j]+" "); } // System.out.println(); } } public int solve(){ boolean[] searched = new boolean[size]; Arrays.fill(searched, false); searched[0] = true; int ret = search(0, 0, 1, searched); if(ret==Integer.MAX_VALUE) ret = -1; return ret; } private int search(int loc, int len, int snum, boolean[] searched){ if(snum==size){ max = Math.min(max, len); return len; } else{ if(len>=max) return max; int ret = Integer.MAX_VALUE; for(int i=0;i<size;i++){ if(!searched[i]&&dist[loc][i]>=0){ searched[i] = true; ret = Math.min(ret, search(i, len + dist[loc][i], snum + 1, searched)); searched[i] = false; } } return ret; } } } class Point{ int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。