fiveinarow_felicia.java

第四届百度杯预赛解题报告 武汉大学20090315

import java.io.*;
import java.util.*;

public class Five {
	final static int dx[] = {0, 1, 1, 1};
	final static int dy[] = {1, 1, 0, -1};
	static int g[][] = new int[15][15];
	static int cnt_b;
	static int cnt_w;

	static boolean ok(final int x, final int y) {
	    return x >= 0 && x < 15 && y >= 0 && y < 15;
	}
	
	static boolean five(final int x, final int y) {
	    for (int i = 0; i < 4; i++) {
	        int j;
	        for (j = 1; j < 5; j++) {
	            int nx = x + j * dx[i];
	            int ny = y + j * dy[i];
	            if (!ok(nx, ny))
	                break;
	            if (g[nx][ny] != g[x][y])
	                break;
	        }
	        if (j == 5)
	            return true;
	    }
	    return false;
	}

	static int win() {
	    int next;
	    if (cnt_b == cnt_w) {
	        next = 1;
	    }
	    else {
	        next = -1;
	    }
	    for (int x = 0; x < 15; x++)
	        for (int y = 0; y < 15; y++)
	            if (g[x][y] != 0 && five(x, y))
	                return 0;

	    for (int i = 0; i < 15; i++)
	        for (int j = 0; j < 15; j++) {
	            if (g[i][j] == 0) {
	                g[i][j] = next;
	                for (int x = 0; x < 15; x++)
	                    for (int y = 0; y < 15; y++)
	                        if (g[x][y] != 0 && five(x, y))
	                            return next;
	                g[i][j] = 0;
	            }
	        }
	    return 0;
	}
	public static void main(String args[]) throws Exception {
		Scanner cin = new Scanner(System.in);
                int ca = cin.nextInt();
	    while (ca > 0) {
                ca--;
	        cnt_b = 0;
	        cnt_w = 0;
	        for (int i = 0; i < 15; i++) {
	        	String s = cin.next();
	            for (int j = 0; j < 15; j++) {
	            	if (s.charAt(j) == 'B') {
	            		g[i][j] = 1;
	            	} else if (s.charAt(j) == 'W') {
	            		g[i][j] = -1;
	            	} else {
	            		g[i][j] = 0;
	            	}
	                if (g[i][j] == 1)
	                    cnt_b++;
	                if (g[i][j] == -1)
	                    cnt_w++;
	            }
	        }
	        int ret = win();
	        if (ret != 0)
	            System.out.println("YES");
	        else
	        	System.out.println("NO");
	    }
	}
}