现在的位置: 首页 > 综合 > 正文

查找同色围棋子的广度和深度遍历方法

2013年05月04日 ⁄ 综合 ⁄ 共 4901字 ⁄ 字号 小 中 大 ⁄ 评论关闭
原文地址：http://www.java2000.net/p9798

从A点开始进行4方向遍历

目的是找到和A点相连并且拥有相同棋面的棋子个数

  1. package net.java2000.ag;
  3. import java.awt.Point;
  4. import java.util.ArrayList;
  5. import java.util.List;
  7. /**
  8.  * 查找同色围棋子的广度遍历方法。
  9.  * 
  10.  * @author 赵学庆，Java世纪网(java2000.net)
  11.  * 
  12.  */
  13. public class ChessWideTraversal {
  16.   static char[][] chess = { { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  17.     { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  18.     { '1', '1', '1', '1', '0', '0', '0', '1', '1' },
  19.     { '1', '1', '1', '1', '0', '1', '0', '1', '1' },
  20.     { '1', '0', '0', '1', 'A', '1', '1', '1', '1' },
  21.     { '1', '1', '0', '0', '0', '1', '1', '1', '1' },
  22.     { '1', '1', '1', '1', '0', '1', '1', '1', '1' },
  23.     { '1', '1', '1', '1', '0', '1', '1', '1', '1' },
  24.     { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  25.     { '1', '1', '1', '1', '1', '1', '1', '1', '1' } };
  26.   
  28.   // 如果已经遍历了，则不再重复
  29.   static boolean[][] haveFound = new boolean[chess.length][chess[0].length];
  31.   /**
  32.    * 被查找的广度遍历。
  33.    * 
  34.    * @param x
  35.    *          种子横坐标
  36.    * @param y
  37.    *          种子纵坐标
  38.    * @param sign
  39.    *          颜色
  40.    * @return 同色数组
  41.    */
  42.   public static List<Point> find(int x, int y, char sign) {
  43.     List<Point> list = new ArrayList<Point>();
  44.     Point p = new Point(x, y);
  45.     list.add(p); // 起始的种子
  46.     for (int i = 0; i < list.size(); i++) {
  47.       p = list.get(i);// 当前位置
  49.       // 左侧，没有到边界
  50.       if (p.x > 0) {
  51.         // 数值等于0 且没有找过
  52.         if (chess[p.y][p.x - 1] == sign && !haveFound[p.y][p.x - 1]) {
  53.           list.add(new Point(p.x - 1, p.y));
  54.           haveFound[p.y][p.x - 1] = true;
  55.         }
  56.       }
  58.       // 上侧，没有到边界
  59.       if (p.y > 0) {
  60.         // 数值等于0 且没有找过
  61.         if (chess[p.y - 1][p.x] == sign && !haveFound[p.y - 1][p.x]) {
  62.           list.add(new Point(p.x, p.y - 1));
  63.           haveFound[p.y - 1][p.x] = true;
  64.         }
  65.       }
  67.       // 右侧，没有到边界
  68.       if (p.x < chess[0].length - 1) {
  69.         // 数值等于0 且没有找过
  70.         if (chess[p.y][p.x + 1] == sign && !haveFound[p.y][p.x + 1]) {
  71.           list.add(new Point(p.x + 1, p.y));
  72.           haveFound[p.y][p.x + 1] = true;
  73.         }
  74.       }
  76.       // 下侧，没有到边界
  77.       if (p.y < chess[0].length - 1) {
  78.         // 数值等于0 且没有找过
  79.         if (chess[p.y + 1][p.x] == sign && !haveFound[p.y + 1][p.x]) {
  80.           list.add(new Point(p.x, p.y + 1));
  81.           haveFound[p.y + 1][p.x] = true;
  82.         }
  83.       }
  84.     }
  85.     return list;
  86.   }
  88.   /**
  89.    * 以图形形式显示遍历结果
  90.    */
  91.   private static void printGraph() {
  92.     for (int i = 0; i < chess.length; i++) {
  93.       for (int j = 0; j < chess[0].length; j++) {
  94.         System.out.print(haveFound[i][j] ? '*' : ' ');
  95.       }
  96.       System.out.println();
  97.     }
  98.   }
  99.   
  100.   public static void main(String[] args) {
  101.     List<Point> list = find(4, 4, '0');
  102.     printGraph();
  103.     for (Point p : list) {
  104.       System.out.println(p.x + "," + p.y);
  105.     }
  106.   }
  108. }

运行结果

        
        
    *** 
    * * 
 **     
  ***   
    *   
    *   
        
        
4,4
4,3
4,5
4,2
3,5
4,6
5,2
2,5
4,7
6,2
2,4
6,3
1,4
   

  1. package net.java2000.ag;
  3. /**
  4.  * 查找同色围棋子的深度遍历方法
  5.  * 
  6.  * @author xifo，Java世纪网(java2000.net)
  7.  * 
  8.  */
  9. public class ChessDeepTraversal {
  10.   private char[][] layout = { { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  11.       { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  12.       { '1', '1', '1', '1', '0', '0', '0', '1', '1' },
  13.       { '1', '1', '1', '1', '0', '1', '0', '1', '1' },
  14.       { '1', '0', '0', '1', 'A', '1', '1', '1', '1' },
  15.       { '1', '1', '0', '0', '0', '1', '1', '1', '1' },
  16.       { '1', '1', '1', '1', '0', '1', '1', '1', '1' },
  17.       { '1', '1', '1', '1', '0', '1', '1', '1', '1' },
  18.       { '1', '1', '1', '1', '1', '1', '1', '1', '1' },
  19.       { '1', '1', '1', '1', '1', '1', '1', '1', '1' } };
  21.   // 9行 10列
  22.   private int w = 9, h = 10;
  23.   private boolean[][] flag = new boolean[h][w];
  25.   /**
  26.    * 以 x, y 为起点进行深度优先遍历
  27.    */
  28.   private void traverse(int x, int y) {
  29.     flag[x][y] = true;
  31.     // 尝试遍历左侧结点
  32.     if(x > 0 && !flag[x-1][y] && layout[x-1][y] == '0'){
  33.       traverse(x - 1, y);
  34.     }
  36.     // 尝试遍历上侧结点
  37.     if(y > 0 && !flag[x][y-1] && layout[x][y-1] == '0'){
  38.       traverse(x, y - 1);
  39.     }
  41.     // 尝试遍历右侧结点
  42.     if(x < w - 1 && !flag[x + 1][y] && layout[x + 1][y] == '0'){
  43.       traverse(x + 1, y);
  44.     }
  46.     // 尝试遍历下侧结点
  47.     if(y < h - 1 && !flag[x][y + 1] && layout[x][y + 1] == '0'){
  48.       traverse(x, y + 1);
  49.     }
  50.   }
  52.   /**
  53.    * 以图形形式显示遍历结果
  54.    */
  55.   private void printGraph() {
  56.     for (int i = 0; i < h; i++) {
  57.       for (int j = 0; j < w; j++) {
  58.         System.out.print(flag[i][j] ? '*' : ' ');
  59.       }
  60.       System.out.println();
  61.     }
  62.   }
  64.   /**
  65.    * 以坐标形式显示遍历结果
  66.    */
  67.   private void printCoordinates() {
  68.     System.out.println("遍历到的结点坐标：");
  69.     for (int i = 0; i < h; i++) {
  70.       for (int j = 0; j < w; j++) {
  71.         System.out.print(flag[i][j] ? (j + ", " + i + "/n") : "");
  72.       }
  73.     }
  74.   }
  76.   public static void main(String[] args) {
  77.     // 遍历起点坐标
  78.     int x = 4, y = 4;
  79.     ChessDeepTraversal cdt = new ChessDeepTraversal();
  80.     cdt.traverse(x, y);
  81.     cdt.printGraph();
  82.     cdt.printCoordinates();
  83.   }
  84. }

     
   运行结果

        
        
    *** 
    * * 
 ** *   
  ***   
    *   
    *   
        
        
遍历到的结点坐标：
4, 2
5, 2
6, 2
4, 3
6, 3
1, 4
2, 4
4, 4
2, 5
3, 5
4, 5
4, 6
4, 7
     

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞