题解 | #五子棋#

NowCoder最近爱上了五子棋，现在给你一个棋局，请你帮忙判断其中有没有五子连珠（超过五颗也算）。

输入描述:

输入有多组数据，每组数据为一张20x20的棋盘。

其中黑子用“*”表示，白子用“+”表示，空白位置用“.”表示。

输出描述:

如果棋盘上存在五子连珠（无论哪种颜色的棋子），输入“Yes”，否则输出“No”。

输入解释：

每组20个数据，每个数据由一个20个符号的字符串组成。

思路说明：

遍历每一行每一个列，然后在每一个位置处，如果它是* 或 +，就遍历它横向，纵向， 撇向（右上到左下），捺向（左上，右下）四个方向，每一个方向遍历到与它同符号， 就计数加一。

代码解释：

import java.util.*;
public class Main{
  // 用来统计每一个位置四个方向的* 或 + 数量
    public static int count(String[] arr,int m,int n,char ch){
     // 定义一个三维数组，四个方向，每个方向分相对的两个小方向，每个小方向分X和Y坐标
        int[][][]direction ={
            {{0,-1},{0,1}}, // 左 和 右
            {{-1,0},{1,0}}, // 上 和 下
            {{-1,1},{1,-1}}, // 右上 和 左下
            {{-1,-1},{1,1}} // 左上 和 右下
        };
    // 用来记录四个方向的最大值    
        int result =0;
     // 遍历四个方向   
        for(int i=0;i<4;i++){
       // 每个方向 统计一下* 或 + 的次数 
            int total = 0;
       // 依次统计两个小方向的次数 
            for(int j=0;j<2;j++){
       // 统计两个小方向时，都要从起始位置开始 
                int tx = m;  // 起始位置的X
                int ty = n; // 起始位置的y
           // 从起始位置，沿着一个小方向一直遍历（比如一直遍历左边）  
                for(int k=0;;k++){
               // 如果往左遍历，则 x 加上 横向左边的x 
                    tx = tx+direction[i][j][0];
                     // 如果往左遍历，则 y加上 横向左边的y 
                    ty = ty+direction[i][j][1];
                 // 如果当前遍历位置的X或者Y 没有越界，并且当前位置的符号与起始位置的符号
                    // 相等，则数量加一
                    if(tx >=0 && tx<20 && ty>=0 && ty<20
                       && arr[tx].charAt(ty)== ch){
                        total++;
                     // 反之则退出当前小方向的遍历   
                    }else{
                        break;
                    }
                }
                
            }
            // 拿到四个方向的最大值
            result =Math.max(result,total+1);
        }
        return result;
    }
    
    public static boolean goBang(String[] arr,int m,int n){
     // 遍历每一个位置，如果是* 或者 + ，则遍历四个方向
        for(int i=0;i< m;i++){
            for(int j=0;j<n;j++){
                char ch = arr[i].charAt(j);
                if(ch == '*' || ch=='+'){
                // 任意一个方向返回的* 或+ 次数大于等于5次，就寻找结束
                     if(count(arr,i,j,ch) >= 5)
                    return true;
                }
               
            }
        }
       // 遍历完所有位置的四个方向，依然没有一个符号的次数大于等于五次，就返回false 
        return false;
        
    }
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            String[] arr = new String[20];
            for(int i=0;i<20;i++){
                arr[i] = scan.next();
            }
            System.out.println(goBang(arr,20,20)?"Yes":"No");
        }
    }
}