プロフィール

島田圭二

Author:島田圭二
Follow shimanp on Twitter

カレンダー
10 | 2017/03 | 11
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31 -
読断と変見内検索
訪問ありがとうございます
最近のコメント
最近のトラックバック
関連リンク
カテゴリー
月別アーカイブ


スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)
Java - 迷路の最短距離を求める
プログラマーとしての技量を測るという問題があったので挑戦してみた。
人材獲得作戦・4 試験問題ほか - 人生を書き換える者すらいた。
壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ
三時間以内にできれば優秀かもしれないらしい。
とりあえずソース
package src;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Shortest {
private static final char WAY = '$';
private static final char S = 'S';
private static final char G = 'G';

private Stack st = new Stack();
private int goalCnt = 0;
Stack shortest = null;

public static void main(String[] args) {
Shortest sht = new Shortest();
sht.way(args[0]);
}

private void way(String inputPath) {
try {
// char配列に読み込む
char[][] inpMap = inputFile2char2D(inputPath);
Point s = getPoint(inpMap, S);

gotoGoal(s.x, s.y, mapCopy(inpMap));
System.out.println("経路数:" + goalCnt);

if (shortest != null) {
//経路を記述
for(int[] yx : shortest){
inpMap[yx[0]][yx[1]] = WAY;
}
}
print2DChar(inpMap);
outputFile4char2D("output.txt", inpMap);
} catch (Exception ex) {
ex.printStackTrace();
}
}

private void gotoGoal(int x, int y, char[][] map) {
// ゴールだったら終了
if (map[y][x] == G) {
if(shortest == null)shortest = copyStack(st);
if(shortest.size() > st.size())shortest = copyStack(st);
goalCnt++;
return;
}
if (map[y][x] != S) map[y][x] = WAY;
int[] yx = {y,x};
//スタックにつむ
st.push(yx);
// System.out.println("x=" + x + ",y=" + y);
if (map[y-1][x] == ' ' || map[y-1][x] == G) gotoGoal(x, y-1, map);
if (map[y+1][x] == ' ' || map[y+1][x] == G) gotoGoal(x, y+1, map);
if (map[y][x-1] == ' ' || map[y][x-1] == G) gotoGoal(x-1, y, map);
if (map[y][x+1] == ' ' || map[y][x+1] == G) gotoGoal(x+1, y, map);
//全方向だめな場合は終了
map[y][x] = ' ';
//スタックから出す
st.pop();
return;
}

private Point getPoint(char[][] arg2D, char c) {
Point p = new Point(-1, -1);
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
int len2D = arg2D[i].length;
for (int j = 0; j < len2D; j++) {
if (arg2D[i][j] == c) {
p.y = i;
p.x = j;
return p;
}
}
}
return p;
}

private char[][] inputFile2char2D(final String path) throws Exception {
char[][] arg = null;
try {

FileInputStream fi = new FileInputStream(path);
InputStreamReader ir = new InputStreamReader(fi);
BufferedReader br = new BufferedReader(ir);

String line;
List lines = new ArrayList();
int row = 0;
while ((line = br.readLine()) != null) {
lines.add(line);
row++;
}
arg = new char[row][];
int r = 0;
for (String l : lines) {
arg[r++] = l.toCharArray();
}
fi.close();
ir.close();
br.close();
} catch (Exception ex) {
throw ex;
}
return arg;
}

private char[][] mapCopy(char[][] map) {
int map2Dlen = map.length;
char[][] copy = new char[map2Dlen][];

for (int i = 0; i < map2Dlen; i++) {
copy[i] = new char[map[i].length];
System.arraycopy(map[i], 0, copy[i], 0, map[i].length);
}
return copy;
}

private Stack copyStack(Stack s){
Stack copy = new Stack();
for(int[] xy : s){
int[] c = new int[2];
c[0] = xy[0];
c[1] = xy[1];
copy.push(c);
}
return copy;
}

private void outputFile4char2D(final String path, final char[][] arg2D)
throws Exception {
FileOutputStream fo = new FileOutputStream(path);
OutputStreamWriter ow = new OutputStreamWriter(fo);
BufferedWriter bw = new BufferedWriter(ow);
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
bw.write(arg2D[i]);
bw.newLine();
}
bw.close();
}

private void print2DChar(final char[][] arg2D) {
int len1D = arg2D.length;
for (int i = 0; i < len1D; i++) {
System.out.println(arg2D[i]);
}
}

}


一応書いてみたけど、どうやらこれだと、全経路を通ってからチェックするので、
不完全な最短チェックらしく、レベル3ということみたい。。。
まだまだだな・・・。
っていうか、全経路を通らずにどうやってチェックするんだろう?
後でググってみよう。
スポンサーサイト


アルゴリズム | 【2010-04-09(Fri) 14:08:49】 | Trackback:(0) | Comments:(1)
コメント
このコメントは管理者の承認待ちです
2011-04-03 日 13:21:30 | | # [ 編集]
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。