Jadi tujuannya adalah untuk mencetak semua angka yang mungkin yang digitnya dapat dibentuk oleh urutan karakter yang berdekatan pada papan menggunakan DFS. Dengan berdekatan maksud saya bersebelahan, baik secara vertikal, ...

2
F11 6 April 2021, 00:24

1 menjawab

Jawaban Terbaik

Anda harus dapat memang dapat mencapai output yang diharapkan tanpa membuat salinan matriks yang dikunjungi.

Yang penting adalah mengatur visited[row][col] ke false setelah setiap kunjungan lengkap di jalur .

Contoh:

Katakanlah Anda telah melintasi '12' dan sekarang memiliki '3' dan '4' tersisa untuk dikunjungi. Dalam keadaan saat ini, visited Nilai matriks untuk '1' dan '2' diatur ke true dan untuk '3' dan '4' diatur ke FALSE. Setelah Anda selesai menghasilkan semua string yang dimulai dengan '12', Anda akan mulai melihat semua string dimulai dengan '13'.

Tapi lihat apa yang terjadi di sini! Anda telah menetapkan nilai '2' yang dikunjungi menjadi benar, dan tidak ada string masa depan yang mengandung '2' yang akan dihasilkan.

Inilah sebabnya mengapa Anda harus mengatur visited[row][col] ke false setelah Anda selesai menghasilkan semua jalur dari titik itu dan seterusnya.

Untuk benar-benar memahami ini, lacak kode Anda dengan pena dan kertas dan Anda akan mengingatnya dengan lebih baik.

Catatan:

Pada kenyataannya, dalam contoh yang dijelaskan di atas, Anda tidak akan pernah menghasilkan string yang dimulai dengan '13' karena visited[1][1] akan diatur ke true sebelumnya dan 3 tidak akan pernah tercapai lagi. Saya mengabaikan fakta itu untuk mengilustrasikan suatu poin.

Mengapa saya menyarankan untuk tidak membuat salinan yang mendalam dari setiap panggilan rekursif? Sederhana, untuk menghemat waktu dan ruang. Setiap panggilan akan mengambil o (m * n) ruang dan waktu untuk menghasilkan dan menyimpan matriks yang dikunjungi baru.

Berikut adalah satu varian dari kode yang benar:

import java.util.*;

public class DFS{

    static char[][] grid;
    static int rows;
    static int columns;

    public static void main(String[] args) {
        //test grid. made it small so that solutions are easy to count
        grid = new char[][]{
                new char[]{'1', '2'},
                new char[]{'3','4'},
        };
        rows = grid.length;
        columns = grid[0].length;
        ArrayList<String>list = new ArrayList<>();
        dfs(0, 0, new boolean[rows][columns], new StringBuilder());
        //System.out.println(list);
    }

    public static void dfs(int row, int col, boolean[][] visited, StringBuilder builder){
        visited[row][col] = true;
        builder.append(grid[row][col]);
        System.out.println(builder);

        for(int x = -1; x <= 1; x++){
            for(int y = -1; y <= 1; y++){
                //index bounds check
                if((row + x >= 0) && (row + x < rows) && (col + y >= 0) && (col + y < columns)){
                    if(!visited[row + x][col + y]){
                        dfs(row + x, col + y, visited, builder);
                    }

                }
            }
        }
        visited[row][col]=false;
        builder.deleteCharAt(builder.length()-1);
    }
}
2
rahs 5 April 2021, 22:15