M-Judge 10158 Dungeon Wall

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

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