深度优先搜索学习五例之五（JAVA）

一、深度优先搜索遍历磁盘文件目录

import java.io.File;
import java.io.IOException;
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
public class ListFile{
        public static void main(String[] args) throws IOException {
              File file = new File("c:/java");
               DFS1(file);
               System.out.println("--------------------------------------");
               System.out.println("--------------------------------------");
                DFS2(file);
              
        }
        // 文件深度优先遍历，栈实现
        private static void DFS1(File file) throws IOException {
               Stack< File> stack = new Stack< File>();
               stack.push(file);//当前目录进栈
               File fileInStack = null;
             while (!stack.isEmpty()) {
              fileInStack = stack.pop();
              System.out.println("dir:" + fileInStack.getCanonicalPath());//访问当前目录
              File[] files = fileInStack.listFiles();//当前目录的所有邻接点
                 for (File eachFile : files) {
                    if (eachFile.isFile()) {
                        System.out.println("file:" + eachFile.getCanonicalPath());
                    } else {
                         stack.push(eachFile);//邻接点进栈
                    }
                  }
                }
        }

        // 文件深度递归遍历
        private static void DFS2(File file) throws IOException {
             System.out.println("dir:" + file.getCanonicalPath());
             File[] files = file.listFiles();
             for (File eachFile : files) {
               if (eachFile.isFile()) {
                   System.out.println("file:" + eachFile.getCanonicalPath());
               } else {
                   DFS2(eachFile);
                 
             }
          }
     }
     
}

二、POJ 1501
题意：给出一个字符矩阵和多行单词，然后看字符矩阵中是否有和这些单词匹配的单词，只能按照直线（横、竖、斜）进行匹配，如果匹配成功则输出首字母和末字母匹配成功的位置，没有则输出Not found。样例如下：

Sample Input

5
EDEEE
DISKE
ESEEE
ECEEE
EEEEE
DISC
DISK
DISP
0
Sample Output

1,2 4,2
2,1 2,4
Not found


思路：遍历字符矩阵中的每一个字符，看其是否与所给单词的第一字符相同，如果相同则DSF继续搜索下一个字母。

import java.util.Arrays;
import java.util.Scanner;
public class Main{
 private char c[][];  //字符矩阵
 private int n;  //字符矩阵的大小n*n
 private String s;//在字符中要找的单词
 private boolean flag;//匹配成功的标志
 private boolean vis[][];  //状态数组
 private int sx,sy,ex,ey;//匹配成功后，首字母和末字母匹配成功的位置

 private int dir[][]={{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};  

   public Main(int n,String s,char[][] c){
      this.n=n;
      this.s=s;
      this.c=c;
      flag=false;
      vis=new boolean[n][n];
   }


  private void dfs(int i,int j,int m,int k) {  
    int x,y;  
    if(flag) return;  
     //深搜结束条件,必须加个m==s.length()因为给出的字符串可能有重复字母   

      if((c[i][j]==s.charAt(s.length()-1))&&m==s.length()) {  
      ex=i;ey=j;  //记录匹配成功末字符位置
      flag=true;   
      return;  
     }  
    x=i+dir[k][0];  
    y=j+dir[k][1];  
    if(x>=0&&x<n&&y>=0&&y<n&&c[x][y]==s.charAt(m)&&!vis[x][y])  
    {  
      vis[x][y]=true;  
      dfs(x,y,m+1,k);  //同一方向，搜索下一个字符
      vis[x][y]=false;  
    }  
  }  
  
   public static void main(String args[]){ 
     Scanner in=new Scanner(System.in);
     String s="";
     int n=in.nextInt();  
     char[][] c=new char[n][n];
 
     for(int i=0;i<n;i++){
      s=in.next();
       for(int j=0;j<n;j++)
          c[i][j]=s.charAt(j);
      }

     
     while(true)  { 
      s=in.next();
      if(s.equals("0")) break;  
       Main main=new Main(n,s,c);
       main.go();
     }
   }

 private void go(){
  
     for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)  
         if(c[i][j]==s.charAt(0)){//找到第一个字母后，按同一个方向搜索   
           for(int k=0;k<8;k++){  
             dfs(i,j,1,k);  
             if(flag)   
             {   
               sx=i;sy=j;   
               System.out.printf("%d,%d %d,%d\n",sx+1,sy+1,ex+1,ey+1); 
               return;
             }  
           }  
         }  
      
       if(!flag) System.out.printf("Not found\n");  
   }  
  
}