人間の(x、y)座標を入力
人間の表示：☆
添付画像：黄色が出口、白が通路、「赤、オレンジ」が火災。
本当の最短では無いので、本当の最短を目指すなら2手先を読だほうが良いでしょいうが、2手先の最短の判定だと1手先に障害物が有る場合も想定しなければならないので、その分 処理が複雑になる。
a3iFieldは出口より遠い方が数値が大きくなる、分かりやすく言うと数値は出口との距離と考えると分かりやすい(数学的な意味での距離では無い)、出口ごとに個々に計算している。
(水の波紋のように)角で回り込んでいる事に注意、そうしないと複雑な経路では対応できない。
波紋の数値の表示は1桁目だけの表示だが、デバッグ用ならその波紋のイメージさえわかれば良いので問題ない。
注意点としては、このデモでは斜めでも移動できるので、それが問題になる、下記の場合でも４から３に移動できる。
３□
□４
>(水の波紋のように)角で回り込んでいる事に注意、そうしないと複雑な経路では対応できない。
2番目の添付画像の情況で青の地点に人が居る場合など。
このデモでa2iMapに、実際にそのデータを入れて試してみると良いでしょう。
import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int iManX = -1;
static int iManY = -1;
public static void main(String[] args) {
Scanner SC = new Scanner(System.in);
int[][] a2iMap = {
{ 0, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 1, 0 },
{ 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2 },
{ 1, 1, 2, 2, 3, 3, 2, 2, 2, 1, 1, 2, 2 },
{ 1, 2, 2, 2, 3, 3, 2, 2, 1, 1, 2, 2, 2 },
{ 1, 2, 2, 2, 3, 3, 3, 1, 1, 2, 2, 2, 2 },
{ 1, 1, 2, 2, 3, 3, 1, 1, 2, 2, 2, 2, 2 },
{ 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2 },
{ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2 },
{ 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2 },
};
Display_Map(a2iMap);
int iMapH = a2iMap.length;
int iMapW = a2iMap[0].length;
ArrayList<Point> d1aExit = new ArrayList<Point>();
int iExitQnt = 0;
int iExitCnt = 0;
for (int y = 0; y < a2iMap.length; y++) {
for (int x = 0; x < a2iMap[y].length; x++) {
switch (a2iMap[y][x]) {
case 0:
d1aExit.add(new Point(x, y));
iExitQnt++;
break;
}
}
}
int[][] a2iLog = new int[iMapH][iMapW];
int[][][] a3iField = new int[iExitQnt][iMapH][iMapW];
for (int i = 0; i < a3iField.length; i++) {
for (int y = 0; y < a3iField[i].length; y++) {
for (int x = 0; x < a3iField[i][y].length; x++) {
if (a2iMap[y][x] <= 1) {
a3iField[i][y][x] = Integer.MAX_VALUE;
} else {
a3iField[i][y][x] = -1;
}
}
}
/*
System.out.printf("iExitCnt: %d, %n", i);
Display_Field(a3iField[i]);
*/
}
for (iExitCnt = 0; iExitCnt < iExitQnt; iExitCnt++) {
int dist = 0;
ArrayList<Point> d1aRipples = new ArrayList<Point>();
d1aRipples.add(d1aExit.get(iExitCnt));
Point p = d1aRipples.get(0);
a3iField[iExitCnt][p.y][p.x] = dist;
System.out.printf("iExitCnt: %d, p: %s, %n", iExitCnt, p);
while (0 < d1aRipples.size()) {
// System.out.println("while (0 < d1aRipples.size())");
ArrayList<Point> d1aRipNext = new ArrayList<Point>();
dist++;
for (Point rp : d1aRipples) {
for (int j = 0; j < 9; j++) {
int dx = j % 3 - 1;
int dy = j / 3 - 1;
int cx = rp.x + dx;
int cy = rp.y + dy;
if (0 <= cx & cx < iMapW & 0 <= cy & cy < iMapH) {
// System.out.println("if (0<=cx<iMapW & 0<=cy<iMapH)");
int pres = a3iField[iExitCnt][cy][cx];
// System.out.printf("pres: %d, dist: %d, %n", pres, dist);
if (pres > dist) {
// System.out.println("if (pres > dist)");
a3iField[iExitCnt][cy][cx] = dist;
d1aRipNext.add(new Point(cx, cy));
}
}
}
}
d1aRipples = d1aRipNext;
/*
System.out.printf("iExitCnt: %d, %n", iExitCnt);
Display_Field(a3iField[iExitCnt]);
*/
}
Display_Field(a3iField[iExitCnt]);
}
System.out.println("Input：人間の(x,y)座標");
iManX = SC.nextInt();
iManY = SC.nextInt();
boolean normal = Display_Map(a2iMap);
if (!normal) {
System.out.println("人間を配置できない(x,y)座標が指定されました");
System.exit(255);
}
escape:while (true) {
a2iLog[iManY][iManX] = 1;
Point mp = null;
int min = Integer.MAX_VALUE;
iExitCnt = -1;
for (int k = 0; k < iExitQnt; k++) {
// System.out.printf("k(iExitCnt): %d,%n", k);
// System.out.printf("iManX: %d, iManY: %d, %n", iManX, iManY);
for (int j = 0; j < 9; j++) {
int dx = j % 3 - 1;
int dy = j / 3 - 1;
int cx = iManX + dx;
int cy = iManY + dy;
if (0 <= cx & cx < iMapW & 0 <= cy & cy < iMapH) {
/*
System.out.printf(
"cx: %d, cy: %d, a3iField[k][cy][cx]: %d, %n",
cx,
cy,
a3iField[k][cy][cx]
);
*/
if (a2iLog[cy][cx] == 0) {
int fd = a3iField[k][cy][cx];
if (0 <= fd & fd < min) {
iExitCnt = k;
min = a3iField[k][cy][cx];
mp = new Point(cx, cy);
}
}
}
}
}
iManX = mp.x;
iManY = mp.y;
System.out.printf("iManX: %d, iManY: %d, %n", iManX, iManY);
System.out.printf("iExitCnt: %d, min: %d, %n", iExitCnt, min);
Display_Field(a3iField[iExitCnt]);
if (min == 0) {
break;
}
}
}
static void Display_Field(int[][] field) {
for (int y = 0; y < field.length; y++) {
for (int x = 0; x < field[y].length; x++) {
int cell = field[y][x];
String sCell = "０１２３４５６７８９";
char cCell = ' ';
if (cell == Integer.MAX_VALUE) {
cCell = '■';
} else if (0 <= cell) {
cCell = sCell.charAt(cell % 10);
}
if (iManX == x & iManY == y) {
cCell = '☆';
}
System.out.print(cCell);
}
System.out.println();
}
System.out.println();
}
static boolean Display_Map(int[][] map) {
boolean normal = true; // false; //
for (int y = 0; y < map.length; y++) {
for (int x = 0; x < map[y].length; x++) {
char cCell = '◇';
switch (map[y][x]) {
case 0:
cCell = '★';
break;
case 1:
cCell = '■';
break;
case 2:
cCell = ' ';
break;
case 3:
cCell = '火';
break;
}
if (iManX == x & iManY == y) {
cCell = '☆';
if (2 <= map[y][x]) {
normal = false; // true; //
}
}
System.out.print(cCell);
}
System.out.println();
}
System.out.println();
return normal;
}
}
|
|
掲示板に書き込む前に必ず この ”注意書き”を お読み下さい．
