1130 Alien Security

1130 Alien Security

問題

解答例

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();
        boolean[][] adj = new boolean[n][n];
        for(int i=0;i<n;i++) Arrays.fill(adj[i],false);
        while(sc.hasNext()){
            int p = sc.nextInt();
            int q = sc.nextInt();
            adj[p][q] = true;
        }
        Solver sol = new Solver(n,e,adj);
        System.out.printf("Put guards in room %d.\r\n",sol.solve());
    }
}

class Solver{
    int n;
    int e;
    boolean[][] adj;
    boolean[][] avail;
    Solver(int n, int e, boolean[][] adj) {
        this.n = n;
        this.e = e;
        this.adj = adj;
        this.avail = new boolean[n][n];
    }
    public int solve(){
        analyzeAvailable();
        return nearestPoint();
    }
    private int nearestPoint(){
        Queue<Integer> q = new LinkedList<Integer>();
        boolean[] searched = new boolean[n];
        q.offer(e);
        Arrays.fill(searched,false);
        searched[e] = true;
        while(!q.isEmpty()){
            int v = q.poll();
            if(avail[e][v]) return v;
            for(int i=0;i<n;i++){
                if(adj[i][v]&&!searched[i]){
                    q.offer(i);
                    searched[i] = true;
                }
            }
        }
        return -1;
    }
    private void analyzeAvailable(){
        for(int i=0;i<n;i++) Arrays.fill(avail[i],true);
        for(int k=1;k<n;k++) avail[0][k] = false;
        while(!analyzeAvailableSub());
        for(int i=0;i<n;i++) avail[i][i] = false;
    }
    private boolean analyzeAvailableSub(){
        boolean end = true;
        for(int i=1;i<n;i++){
            boolean[] availnext = new boolean[n];
            Arrays.fill(availnext,false);
            
            boolean first = true;
            for(int p=0;p<n;p++){
                if(adj[p][i]){
                    if(first){
                        for(int k=0;k<n;k++){
                            availnext[k] = avail[p][k];
                        }
                        first = false;
                    }
                    else{
                        for(int k=0;k<n;k++){
                            availnext[k] &= avail[p][k];
                        }
                    }
                }
            }
            availnext[i] = true;
            
            for(int k=0;k<n;k++){
                if(avail[i][k]!=availnext[k]) end = false;
                avail[i][k] = availnext[k];
            }
        }
        return end;
    }
}

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2006年04月16日 23:03
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。