USACO:Overfencing解题报告

思路：Dijkstra求最短路径，然后对于同一出发点求到两个出口之间的较小者，最后对于所有出发点求一个最大值，即所谓的worst point.当然这题在空间上需要优化，用堆来优化是一个可行的办法。其实用一个unsigned char型的数组来记录每两点间距离就可以保证恰好不超空间。当然，网上说可以用floodfill可以更容易得到答案。

 

 

/* ID: xpli1 PROG: maze1 LANG: C */

#include <stdio.h>

#define  VETEXNUM  3801 #define  DIS_MAX   999999

#define max(a,b) (((a) > (b)) ? (a) : (b)) #define min(a,b) (((a) < (b)) ? (a) : (b))

unsigned char square[VETEXNUM][VETEXNUM];        // 初始化为四边封闭 int DA[VETEXNUM]; int DB[VETEXNUM]; int flag[VETEXNUM]; int W,H; char buf[80]; int va,vb;

void DIJ(int* d,int vetexnum,int v0) {  int i,j,v;

 for(i=0; i<vetexnum; i++){      flag[i] = 0;

  d[i] = square[v0][i] < 255 ? square[v0][i]:DIS_MAX;  }

 d[v0] = 0; flag[v0] = 1;

 for(i=1; i<vetexnum; i++){

  int Min = DIS_MAX;

  for(j=0; j<vetexnum; j++){

   if(!flag[j])     if(d[j] < Min) {v = j; Min = d[j];}   }

  flag[v] = 1;

  for(j=0; j<vetexnum; j++){        if(!flag[j] && square[v][j] == 1 && (Min + square[v][j] < d[j])){

    d[j] = Min + square[v][j];    }   }  }  return; }

int main(void) {

 FILE *fin  = fopen ("maze1.in", "r");     FILE *fout = fopen ("maze1.out", "w");

 fscanf(fin,"%d%d/n",&W,&H);    int i,j;

 for(i=0; i<W*H; i++)   for(j=0; j<W*H; j++)    square[i][j] = 255;

 va = vb = -1;

 fgets(buf,sizeof(buf),fin);

 for(j=1; j<2*W; j++) {if(j&1 && buf[j]==' '){if(va == -1) {va = j/2;} else {vb = j/2;}}}

 for(i=1; i<2*H; i++){      fgets(buf,sizeof(buf),fin);      if(i&1 && buf[0] == ' ') {if(va == -1) {va = i/2*W;} else {vb = i/2*W;}}

  if(i&1 && buf[2*W] == ' ') {if(va == -1) {va = i/2*W+W-1;} else {vb = i/2*W+W-1;}}      for(j=1; j<2*W; j++){        if(i&1 && (!(j&1))) {          if(buf[j] == ' ') {            square[(i/2)*W + j/2 -1][(i/2)*W + j/2] = 1;

     square[(i/2)*W + j/2][(i/2)*W + j/2 -1] = 1;          }    }    else if((!(i&1)) && j&1){          if(buf[j] == ' ') {            square[(i/2-1)*W + j/2][(i/2)*W + j/2] = 1;

     square[(i/2)*W + j/2][(i/2-1)*W + j/2] = 1;          }    }   }  }    fgets(buf,sizeof(buf),fin);

 for(j=1; j<2*W; j++) {if(j&1 && buf[j]==' ') {if(va == -1) {va = W*(H-1)+j/2;} else {vb = W*(H-1)+j/2;}}}

 DIJ(DA,W*H,va);

 DIJ(DB,W*H,vb);

 int MAX = -1;  for(i=0; i<W*H; i++)   MAX = max(MAX,min(DA[i],DB[i]));    fprintf(fout,"%d/n",MAX+1);

 return 0; }