M-Judge 10145 Ennichi

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem A: Ennichi
より

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>30;
    final double EPS=1e-9;

    int h, w, n;
    char[][] a;

    void run(){
        h=sc.nextInt();
        w=sc.nextInt();
        n=sc.nextInt();
        a=new char[h][w];
        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                a[j][i]=s.charAt(i);
            }
        }

        for(int j=0; j<h; j++){
            for(int i=0; i<w-1; i++){
                if(a[j][i]==a[j][i+1])
                    continue;

                // swap(i,j)<->(i+1,j)
                char c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;

                if(check()){
                    println("YES");
                    return;
                }

                c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;
            }
        }
        println("NO");
    }

    void show(char[][] a){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+"");
            }
            println("");
        }
    }

    boolean check(){
        boolean[][] clear;
        char[][] a=new char[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                a[j][i]=this.a[j][i];

        for(;;){
            // 落下
            for(int i=0; i<w; i++){
                for(int j=1; j<h; j++){
                    if(a[j][i]!='.')
                        continue;
                    for(int k=j; k>0; k--)
                        a[k][i]=a[k-1][i];
                    a[0][i]='.';
                }
            }

            boolean cl=false;
            clear=new boolean[h][w];

            for(int y=0; y<h; y++){
                for(int x=0; x<w; x++){
                    // (x, y)から縦/横を調べる
                    if(a[y][x]=='.')
                        continue;

                    boolean f=true;
                    for(int y2=y; y2<y+n; y2++){
                        if(y2>=h||a[y2][x]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int y2=y; y2<h&&a[y2][x]==a[y][x]; y2++)
                            clear[y2][x]=true;
                        cl=true;
                    }

                    f=true;
                    for(int x2=x; x2<x+n; x2++){
                        if(x2>=w||a[y][x2]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int x2=x; x2<w&&a[y][x2]==a[y][x]; x2++)
                            clear[y][x2]=true;
                        cl=true;
                    }
                }
            }

            for(int j=0; j<h; j++)
                for(int i=0; i<w; i++)
                    if(clear[j][i])
                        a[j][i]='.';

            if(!cl)
                break;
        }
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                if(a[j][i]!='.')
                    return false;
        return true;
    }

    public static void main(String[] args){
        new Main().run();
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }
}