杭電ACM OJ 1026 Ignatius and the Princess I DFS+BFS

Ignatius and the Princess I

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 20079    Accepted Submission(s): 6540

Special Judge

Problem Description The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:

1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).

2.The array is marked with some characters and numbers. We define them like this:

. : The place where Ignatius can walk on.

X : The place is a trap, Ignatius should not walk on it.

n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.

Input The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.

Output For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.

Sample Input

5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.
        

Sample Output

It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.

   
FINISH

   



   



   
翻譯：

   
.XX.1.

   
..X.2.

   
2...X.

   
...XX.

   
XXXXX.


   
這樣一個迷宮，起點是00 終點是右下角，1,2等數字是怪物。走一步需要1s，殺怪物如果顯示的是1需要1秒，如果2需要2秒，以此類推。

   



   
思路：

   
BFS+優先隊列剪枝 這裡先不剪枝 分别用DFS BFS兩個暴力法做 以後再寫優先隊列剪枝的情況

   



   
DFS就是深度優先搜尋，把一個方向的所有可能都找完了再找另一個方向。十分簡單粗暴。

   
BFS就是廣度優先搜尋，所有的點同時前進。這裡要注意殺怪時間即可，如果怪物時間沒跑完，你是不能繼續走的。

   



   
DFS代碼

   


          
void back(int time, int row, int col) {//origin time = 0//row 行 // col 列

    int killTime = 1;

    if (!a[row][col].equals(".")) {

        killTime += Integer.valueOf(a[row][col]);

    }

    if (col == width - 1 && row == height - 1) {

        min = Math.min(min, killTime + time);

        return;

    }

    for (int i = 0; i < 4; i++) {

        switch (i) {

            case 0:

                int aim = row + 1;
                if (isAccessable(aim, col)) {

                    isAccessed[aim][col] = true;

                    back(time + killTime, aim, col);

                    isAccessed[aim][col] = false;

                }

                break;
            case 1:

                int aim2 = row - 1;
                if (isAccessable(aim2, col)) {

                    isAccessed[aim2][col] = true;

                    back(time + killTime, aim2, col);

                    isAccessed[aim2][col] = false;

                }

                break;
            case 2:

                int aim3 = col + 1;
                if (isAccessable(row, aim3)) {

                    isAccessed[row][aim3] = true;

                    back(time + killTime, row, aim3);

                    isAccessed[row][aim3] = false;

                }

                break;
            case 3:

                int aim4 = col - 1;
                if (isAccessable(row, aim4)) {

                    isAccessed[row][aim4] = true;

                    back(time + killTime, row, aim4);

                    isAccessed[row][aim4] = false;

                }

                break;

        }

    }

}      
        
 
 

 
BFS代碼
 

        
int bfs() {

    int time = 0;

    while (true) {

        time++;

        //對目前點每個元素周遊，檢視是否能生成意願點
        for (int i = 0; i < current.size(); i ++) {

            Point p = current.get(i);
            int row1 = (int) p.getX();
            int col1 = (int) p.getY();
            //debug 這裡的橫坐标 0010101010101010 why？

            if (row1 == height - 1 && col1 == width - 1) {

                return time + 1;

            }

            //如果目前點還有怪物時間，你就不能對任何點産生企圖
            if (flag[row1][col1] > 0) {

                flag[row1][col1]--;

                if (flag[row1][col1] == 0) {

                    flag[row1][col1] = -1;//時間消費光了，标記數組為已走

                }

                //産生企圖,生成will集合,标記數組
            } else if (flag[row1][col1] == -1) {

                //生成意願
                aim(row1 + 1, col1);
                aim(row1 - 1, col1);
                aim(row1, col1 + 1);
                aim(row1, col1 + 1);
                //debug 第二次取就是空的了,很有可能是之後的步驟錯了

            }
        }

        //debug will的size第一次是1，之後一直是0了 1,0
        if (will.size() != 0) {

            for (int j = 0; j < will.size(); j++) {

                Point p1 = will.get(j);
                int row2 = (int) p1.getX();
                int col2 = (int) p1.getY();

                //如果有怪物
                if (!a[row2][col2].equals(".")) {

                    int num = Integer.valueOf(a[row2][col2]);
                    flag[row2][col2] = num;

                }

                flag[row2][col2] = -1;
                current.add(p1);

            }

            will.clear();

        }

    }

}      
        
 
 

 
全部代碼
 

        
package ACM1000_1099;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class IgnatiusAndThePrincessOne1026 {

    IgnatiusAndThePrincessOne1026(String[][] a) {

        height = a.length;
        width = a[0].length;

        this.a = new String[height][width];
        isAccessed = new boolean[height][width];

        for (int i = 0; i < height; i++) {

            for (int j = 0; j < width; j++) {

                this.a[i][j] = a[i][j];

            }

        }

        min = Integer.MAX_VALUE;

//        back(-1, 0, 0);
//
//        System.out.print(min + "");

        //0 未走 -1 已走 -2将走 正數 剩餘時間//是以目前點有兩種情況 -1已走，正數 有倒計時
        flag = new int[height][width];
        current = new ArrayList<>();
        will = new ArrayList<>();

        flag[0][0] = -1;

        Point point = new Point(0, 0);
        current.add(point);

        int result = bfs();
        System.out.print(result + "");

    }

    String[][] a;

    boolean[][] isAccessed;

    int height;

    int width;

    int min;


    int[][] flag;


    List<Point> current;
    List<Point> will;


    boolean isAccessable(int row, int col) {

        if (row < 0 || col < 0 || row > height - 1 || col > width - 1 ||
                a[row][col].equals("X") || isAccessed[row][col]) {

            return false;

        }

        return true;

    }

    //回溯 即 dfs？
    void back(int time, int row, int col) {//origin time = 0//row 行 // col 列

        int killTime = 1;

        if (!a[row][col].equals(".")) {

            killTime += Integer.valueOf(a[row][col]);

        }

        if (col == width - 1 && row == height - 1) {

            min = Math.min(min, killTime + time);

            return;

        }

        for (int i = 0; i < 4; i++) {

            switch (i) {

                case 0:

                    int aim = row + 1;
                    if (isAccessable(aim, col)) {

                        isAccessed[aim][col] = true;

                        back(time + killTime, aim, col);

                        isAccessed[aim][col] = false;

                    }

                    break;
                case 1:

                    int aim2 = row - 1;
                    if (isAccessable(aim2, col)) {

                        isAccessed[aim2][col] = true;

                        back(time + killTime, aim2, col);

                        isAccessed[aim2][col] = false;

                    }

                    break;
                case 2:

                    int aim3 = col + 1;
                    if (isAccessable(row, aim3)) {

                        isAccessed[row][aim3] = true;

                        back(time + killTime, row, aim3);

                        isAccessed[row][aim3] = false;

                    }

                    break;
                case 3:

                    int aim4 = col - 1;
                    if (isAccessable(row, aim4)) {

                        isAccessed[row][aim4] = true;

                        back(time + killTime, row, aim4);

                        isAccessed[row][aim4] = false;

                    }

                    break;

            }

        }

    }


    boolean isWillable(int row, int col) {

        if (row < 0 || col < 0 || row > height - 1 || col > width - 1 ||
                a[row][col].equals("X") || isAccessed[row][col]) {

            return false;

        }

        if (flag[row][col] != -1 && flag[row][col] != -2) {

            return true;

        } else {

            return false;

        }

    }

    void aim(int row, int col) {

        //如果可産生企圖
        if (isWillable(row, col)) {

            flag[row][col] = -2;

            Point p = new Point(row, col);
            will.add(p);

        }

    }

    //優先隊列還不是太明白 但是bfs可以試一下
    int bfs() {

        int time = 0;

        while (true) {

            time++;

            //對目前點每個元素周遊，檢視是否能生成意願點
            for (int i = 0; i < current.size(); i ++) {

                Point p = current.get(i);
                int row1 = (int) p.getX();
                int col1 = (int) p.getY();
                //debug 這裡的橫坐标 0010101010101010 why？

                if (row1 == height - 1 && col1 == width - 1) {

                    return time + 1;

                }

                //如果目前點還有怪物時間，你就不能對任何點産生企圖
                if (flag[row1][col1] > 0) {

                    flag[row1][col1]--;

                    if (flag[row1][col1] == 0) {

                        flag[row1][col1] = -1;//時間消費光了，标記數組為已走

                    }

                    //産生企圖,生成will集合,标記數組
                } else if (flag[row1][col1] == -1) {

                    //生成意願
                    aim(row1 + 1, col1);
                    aim(row1 - 1, col1);
                    aim(row1, col1 + 1);
                    aim(row1, col1 + 1);
                    //debug 第二次取就是空的了,很有可能是之後的步驟錯了

                }
            }

            //debug will的size第一次是1，之後一直是0了 1,0
            if (will.size() != 0) {

                for (int j = 0; j < will.size(); j++) {

                    Point p1 = will.get(j);
                    int row2 = (int) p1.getX();
                    int col2 = (int) p1.getY();

                    //如果有怪物
                    if (!a[row2][col2].equals(".")) {

                        int num = Integer.valueOf(a[row2][col2]);
                        flag[row2][col2] = num;

                    }

                    flag[row2][col2] = -1;
                    current.add(p1);

                }

                will.clear();

            }

        }

    }


    public static void main(final String[] args) throws Exception {

        String[][] a = {
                {".", "X", "X", ".", "1", "."},
                {".", ".", "X", ".", "2", "."},
                {"2", ".", ".", ".", "X", "."},
                {".", ".", ".", "X", "X", "."},
                {"X", "X", "X", "X", "X", "."}};

        IgnatiusAndThePrincessOne1026 i = new IgnatiusAndThePrincessOne1026(a);

    }

}
      
        
 
 

 
這篇文章寫的真爛！但是今天狀态不好。雖然這dfs bfs很快就寫出來了。