M-Judge 10145 Ennichi

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>30;  
11.     final double EPS=1e-9;  
12.   
13.     int h, w, n;  
14.     char[][] a;  
15.   
16.     void run(){  
17.         h=sc.nextInt();  
18.         w=sc.nextInt();  
19.         n=sc.nextInt();  
20.         a=new char[h][w];  
21.         for(int j=0; j<h; j++){  
22.             String s=sc.next();  
23.             for(int i=0; i<w; i++){  
24.                 a[j][i]=s.charAt(i);  
25.             }  
26.         }  
27.   
28.         for(int j=0; j<h; j++){  
29.             for(int i=0; i<w-1; i++){  
30.                 if(a[j][i]==a[j][i+1])  
31.                     continue;  
32.   
33.                 // swap(i,j)<->(i+1,j)  
34.                 char c=a[j][i];  
35.                 a[j][i]=a[j][i+1];  
36.                 a[j][i+1]=c;  
37.   
38.                 if(check()){  
39.                     println("YES");  
40.                     return;  
41.                 }  
42.   
43.                 c=a[j][i];  
44.                 a[j][i]=a[j][i+1];  
45.                 a[j][i+1]=c;  
46.             }  
47.         }  
48.         println("NO");  
49.     }  
50.   
51.     void show(char[][] a){  
52.         for(int j=0; j<h; j++){  
53.             for(int i=0; i<w; i++){  
54.                 print(a[j][i]+"");  
55.             }  
56.             println("");  
57.         }  
58.     }  
59.   
60.     boolean check(){  
61.         boolean[][] clear;  
62.         char[][] a=new char[h][w];  
63.         for(int j=0; j<h; j++)  
64.             for(int i=0; i<w; i++)  
65.                 a[j][i]=this.a[j][i];  
66.   
67.         for(;;){  
68.             // 落下  
69.             for(int i=0; i<w; i++){  
70.                 for(int j=1; j<h; j++){  
71.                     if(a[j][i]!='.')  
72.                         continue;  
73.                     for(int k=j; k>0; k--)  
74.                         a[k][i]=a[k-1][i];  
75.                     a[0][i]='.';  
76.                 }  
77.             }  
78.   
79.             boolean cl=false;  
80.             clear=new boolean[h][w];  
81.   
82.             for(int y=0; y<h; y++){  
83.                 for(int x=0; x<w; x++){  
84.                     // (x, y)から縦/横を調べる  
85.                     if(a[y][x]=='.')  
86.                         continue;  
87.   
88.                     boolean f=true;  
89.                     for(int y2=y; y2<y+n; y2++){  
90.                         if(y2>=h||a[y2][x]!=a[y][x]){  
91.                             f=false;  
92.                             break;  
93.                         }  
94.                     }  
95.                     if(f){  
96.                         for(int y2=y; y2<h&&a[y2][x]==a[y][x]; y2++)  
97.                             clear[y2][x]=true;  
98.                         cl=true;  
99.                     }  
100.   
101.                     f=true;  
102.                     for(int x2=x; x2<x+n; x2++){  
103.                         if(x2>=w||a[y][x2]!=a[y][x]){  
104.                             f=false;  
105.                             break;  
106.                         }  
107.                     }  
108.                     if(f){  
109.                         for(int x2=x; x2<w&&a[y][x2]==a[y][x]; x2++)  
110.                             clear[y][x2]=true;  
111.                         cl=true;  
112.                     }  
113.                 }  
114.             }  
115.   
116.             for(int j=0; j<h; j++)  
117.                 for(int i=0; i<w; i++)  
118.                     if(clear[j][i])  
119.                         a[j][i]='.';  
120.   
121.             if(!cl)  
122.                 break;  
123.         }  
124.         for(int j=0; j<h; j++)  
125.             for(int i=0; i<w; i++)  
126.                 if(a[j][i]!='.')  
127.                     return false;  
128.         return true;  
129.     }  
130.   
131.     public static void main(String[] args){  
132.         new Main().run();  
133.     }  
134.   
135.     void print(String s){  
136.         System.out.print(s);  
137.     }  
138.   
139.     void println(String s){  
140.         System.out.println(s);  
141.     }  
142.   
143.     void println(){  
144.         System.out.println();  
145.     }  
146. }  

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();
    }
}