M-Judge 10158 Dungeon Wall

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem D: Dungeon Wall
より

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int INF=1>>28;  
10.   
11.     int w, h, n;  
12.     int ix, iy, ox, oy;  
13.   
14.     boolean[][][] can;  
15.     int[] dx={0, 1, 0, -1};  
16.     int[] dy={-1, 0, 1, 0};  
17.   
18.     boolean[][] visited;  
19.     int[][] dist;  
20.     P[][] ps;  
21.   
22.     void run(){  
23.         w=sc.nextInt();  
24.         h=sc.nextInt();  
25.         n=sc.nextInt();  
26.         can=new boolean[h][w][4];  
27.         for(int j=0; j<h; j++)  
28.             for(int i=0; i<w; i++)  
29.                 for(int k=0; k<4; k++)  
30.                     can[j][i][k]=true;  
31.   
32.         for(int j=0; j<h; j++){  
33.             can[j][0][3]=false;  
34.             can[j][w-1][1]=false;  
35.         }  
36.         for(int i=0; i<w; i++){  
37.             can[0][i][0]=false;  
38.             can[h-1][i][2]=false;  
39.         }  
40.   
41.         for(int i=0; i<n; i++){  
42.             int sx=sc.nextInt();  
43.             int sy=sc.nextInt();  
44.             int tx=sc.nextInt();  
45.             int ty=sc.nextInt();  
46.             int x1=Math.min(sx, tx);  
47.             int x2=Math.max(sx, tx);  
48.             int y1=Math.min(sy, ty);  
49.             int y2=Math.max(sy, ty);  
50.   
51.             if(x1==x2){  
52.                 for(int y=y1; y<y2; y++){  
53.                     if(x1>0)  
54.                         can[y][x1-1][1]=false;  
55.                     if(x1<w)  
56.                         can[y][x1][3]=false;  
57.                 }  
58.             }else{  
59.                 // y1==y2  
60.                 for(int x=x1; x<x2; x++){  
61.                     if(y1>0)  
62.                         can[y1-1][x][2]=false;  
63.                     if(y1<h)  
64.                         can[y1][x][0]=false;  
65.                 }  
66.             }  
67.         }  
68.   
69.         ix=sc.nextInt();  
70.         iy=sc.nextInt();  
71.         ox=sc.nextInt();  
72.         oy=sc.nextInt();  
73.   
74.         visited=new boolean[h][w];  
75.         dist=new int[h][w];  
76.         ps=new P[h][w];  
77.         for(int j=0; j<h; j++)  
78.             for(int i=0; i<w; i++)  
79.                 ps[j][i]=new P(i, j);  
80.   
81.         int minDist=bfs();  
82.         int maxdist=minDist;  
83.         for(int j=0; j<h; j++){  
84.             for(int i=0; i<w; i++){  
85.                 if(can[j][i][0]){  
86.                     can[j][i][0]=false;  
87.                     can[j-1][i][2]=false;  
88.                     int d=bfs();  
89.                     if(d!=INF)  
90.                         maxdist=Math.max(maxdist, bfs());  
91.                     can[j][i][0]=true;  
92.                     can[j-1][i][2]=true;  
93.                 }  
94.                 if(can[j][i][1]){  
95.                     can[j][i][1]=false;  
96.                     can[j][i+1][3]=false;  
97.                     int d=bfs();  
98.                     if(d!=INF)  
99.                         maxdist=Math.max(maxdist, bfs());  
100.                     can[j][i][1]=true;  
101.                     can[j][i+1][3]=true;  
102.                 }  
103.             }  
104.         }  
105.         // println(minDist+"");  
106.         // println(maxdist+"");  
107.         println((maxdist-minDist)+"");  
108.     }  
109.   
110.     int bfs(){  
111.         for(int j=0; j<h; j++){  
112.             for(int i=0; i<w; i++){  
113.                 visited[j][i]=false;  
114.                 dist[j][i]=0;  
115.             }  
116.         }  
117.         LinkedList<P> q=new LinkedList<P>();  
118.         q.addLast(ps[iy][ix]);  
119.         visited[iy][ix]=true;  
120.         for(; !q.isEmpty();){  
121.             P p=q.removeFirst();  
122.             if(p.x==ox&&p.y==oy)  
123.                 return dist[p.y][p.x];  
124.             for(int d=0; d<4; d++){  
125.                 int x=p.x+dx[d];  
126.                 int y=p.y+dy[d];  
127.                 if(can[p.y][p.x][d]&&!visited[y][x]){  
128.                     q.addLast(ps[y][x]);  
129.                     visited[y][x]=true;  
130.                     dist[y][x]=dist[p.y][p.x]+1;  
131.                 }  
132.             }  
133.         }  
134.         return INF;  
135.     }  
136.   
137.     class P{  
138.         int x, y;  
139.   
140.         P(int x, int y){  
141.             this.x=x;  
142.             this.y=y;  
143.         }  
144.     }  
145.   
146.     public static void main(String[] args){  
147.         new Main().run();  
148.     }  
149.   
150.     void println(String s){  
151.         System.out.println(s);  
152.     }  
153.   
154.     void print(String s){  
155.         System.out.print(s);  
156.     }  
157. }  

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1>>28;

    int w, h, n;
    int ix, iy, ox, oy;

    boolean[][][] can;
    int[] dx={0, 1, 0, -1};
    int[] dy={-1, 0, 1, 0};

    boolean[][] visited;
    int[][] dist;
    P[][] ps;

    void run(){
        w=sc.nextInt();
        h=sc.nextInt();
        n=sc.nextInt();
        can=new boolean[h][w][4];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                for(int k=0; k<4; k++)
                    can[j][i][k]=true;

        for(int j=0; j<h; j++){
            can[j][0][3]=false;
            can[j][w-1][1]=false;
        }
        for(int i=0; i<w; i++){
            can[0][i][0]=false;
            can[h-1][i][2]=false;
        }

        for(int i=0; i<n; i++){
            int sx=sc.nextInt();
            int sy=sc.nextInt();
            int tx=sc.nextInt();
            int ty=sc.nextInt();
            int x1=Math.min(sx, tx);
            int x2=Math.max(sx, tx);
            int y1=Math.min(sy, ty);
            int y2=Math.max(sy, ty);

            if(x1==x2){
                for(int y=y1; y<y2; y++){
                    if(x1>0)
                        can[y][x1-1][1]=false;
                    if(x1<w)
                        can[y][x1][3]=false;
                }
            }else{
                // y1==y2
                for(int x=x1; x<x2; x++){
                    if(y1>0)
                        can[y1-1][x][2]=false;
                    if(y1<h)
                        can[y1][x][0]=false;
                }
            }
        }

        ix=sc.nextInt();
        iy=sc.nextInt();
        ox=sc.nextInt();
        oy=sc.nextInt();

        visited=new boolean[h][w];
        dist=new int[h][w];
        ps=new P[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                ps[j][i]=new P(i, j);

        int minDist=bfs();
        int maxdist=minDist;
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                if(can[j][i][0]){
                    can[j][i][0]=false;
                    can[j-1][i][2]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][0]=true;
                    can[j-1][i][2]=true;
                }
                if(can[j][i][1]){
                    can[j][i][1]=false;
                    can[j][i+1][3]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][1]=true;
                    can[j][i+1][3]=true;
                }
            }
        }
        // println(minDist+"");
        // println(maxdist+"");
        println((maxdist-minDist)+"");
    }

    int bfs(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                visited[j][i]=false;
                dist[j][i]=0;
            }
        }
        LinkedList<P> q=new LinkedList<P>();
        q.addLast(ps[iy][ix]);
        visited[iy][ix]=true;
        for(; !q.isEmpty();){
            P p=q.removeFirst();
            if(p.x==ox&&p.y==oy)
                return dist[p.y][p.x];
            for(int d=0; d<4; d++){
                int x=p.x+dx[d];
                int y=p.y+dy[d];
                if(can[p.y][p.x][d]&&!visited[y][x]){
                    q.addLast(ps[y][x]);
                    visited[y][x]=true;
                    dist[y][x]=dist[p.y][p.x]+1;
                }
            }
        }
        return INF;
    }

    class P{
        int x, y;

        P(int x, int y){
            this.x=x;
            this.y=y;
        }
    }

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

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

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