結果

問題 No.348 カゴメカゴメ
ユーザー threepipes_s
提出日時 2016-02-27 00:09:53
言語 Java
(openjdk 23)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 5,312 bytes
コンパイル時間 3,067 ms
コンパイル使用メモリ 90,596 KB
実行使用メモリ 95,708 KB
最終ジャッジ日時 2024-09-24 10:43:21
合計ジャッジ時間 23,329 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException,
    IOException {Solve solve = new Solve();solve.solve();}
}
class Solve{
    void dump(int[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]+" ");System.out.println();}
    void dump(int[]a,int n){for(int i=0;i<a.length;i++)System.out.printf("%"+n+"d",a[i]);System.out.println();}
    void dump(long[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]+" ");System.out.println();}
    void dump(char[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]);System.out.println();}
    String itob(int a,int l){return String.format("%"+l+"s",Integer.toBinaryString(a)).replace(' ','0');}
    int n, m;
    void solve() throws NumberFormatException, IOException{
        final ContestScanner in = new ContestScanner();
        Writer out = new Writer();
        n = in.nextInt();
        m = in.nextInt();
        BitSet map = new BitSet(n*m);
        int allx = 0;
        for(int i=0; i<n; i++){
            char[] line = in.nextToken().toCharArray();
            for(int j=0; j<m; j++){
                if(line[j]=='x'){
                    map.set(i*m+j);
                    allx++;
                }
            }
        }
        List<Node> node = new ArrayList<>();
        final int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        final int[] dy = {1, 0, -1, 1, -1, 1, -1, 0};
        final int[] dx4 = {1,0,-1,0};
        final int[] dy4 = {0,1,0,-1};
        BitSet used = new BitSet();
        Stack<Long> oq = new Stack<>();
        Stack<Integer> qu = new Stack<>();
        oq.add(0L);
        int mask = (1<<30)-1;
        int id = 0;
        node.add(new Node(0, 0));
        while(!oq.isEmpty()){
            long ot = oq.pop();
            final int p = (int)ot&mask;
            ot >>= 30;
            if(used.get(p)) continue;
            used.set(p);
            final int y = p/m;
            final int x = p%m;
            if(!map.get(p)){
                for(int i=0; i<4; i++){
                    final int ny = y+dy4[i];
                    final int nx = x+dx4[i];
                    final int np = ny*m+nx;
                    if(out(ny, nx) || used.get(np)) continue;
                    oq.add(np|ot<<30);
                }
            }else{
                id++;
                int left = m;
                int ly = 0;
                int size = 0;
                qu.clear();
                qu.add(p);
                while(!qu.isEmpty()){
                    final int ip = qu.pop();
                    size++;
                    final int iy = ip/m;
                    final int ix = ip%m;
                    if(ix<left && !map.get(iy*m+ix+1)){
                        left = ix;
                        ly = iy;
                    }
                    for(int i=0; i<8; i++){
                        final int ny = iy+dy[i];
                        final int nx = ix+dx[i];
                        final int np = ny*m+nx;
                        if(out(ny, nx) || !map.get(np) || used.get(np))
                            continue;
                        used.set(np);
                        qu.add(np);
                    }
                }
                // p <- node
                if(size>3) oq.add(ly*m+left+1 | (long)id<<30);
                Node newnode = new Node(id, size);
                Node parent = node.get((int)ot);
                node.add(newnode);
                newnode.append(parent);
                parent.append(newnode);
            }
        }
        int x1 = dfs(node.get(0), -1, true);
        System.out.println(Math.max(x1, allx-x1));
    }
    int dfs(Node v, int par, boolean f){
        int sum = 0;
        for(Node nv: v.edge){
            if(nv.id == par) continue;
            sum += dfs(nv, v.id, !f);
        }
        return sum + (f?v.size:0);
    }
    
    boolean out(int y, int x){
        return y<0||y>=n||x<0||x>=m;
    }
}
class Node{
    int id;
    int size;
    List<Node> edge = new ArrayList<>();
    Node(int id, int s){
        this.id = id;
        size = s;
    }
    void append(Node v){
        edge.add(v);
    }
}
class MultiSet<T> extends HashMap<T, Integer>{
    @Override
    public Integer get(Object key){return containsKey(key)?super.get(key):0;}
    public void add(T key,int v){put(key,get(key)+v);}
    public void add(T key){put(key,get(key)+1);}
    public void sub(T key)
    {final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
}
class Timer{
    long time;
    public void set(){time=System.currentTimeMillis();}
    public long stop(){return time=System.currentTimeMillis()-time;}
    public void print()
    {System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");}
    @Override public String toString(){return"Time: "+time+"ms";}
}
class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException{super(System.out);}
}
class ContestScanner {
    private InputStreamReader in;private int c=-2;
    public ContestScanner()throws IOException 
    {in=new InputStreamReader(System.in);}
    public ContestScanner(String filename)throws IOException
    {in=new InputStreamReader(new FileInputStream(filename));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException 
    {return Double.parseDouble(nextToken());}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0