USACO 2.4 Overfencing 【种子染色法+递推】-白红宇

USACO 2.4 Overfencing 【种子染色法+递推】

阅读量：5152 次

发布时间：2019-06-13

本文共 1872 字，大约阅读时间需要 6 分钟。

题在这：

https://www.luogu.org/problem/show?pid=1519

分析：

这个题有以下几个难点：

1、输入时回车的处理

2、奇数行与列不能计数的问题

3、在众多最小值中取最大的逻辑问题

4、单终点最短路径，多次搜索方案优化问题

也同时有以下几个窍门：

1、把字符转化成ASCII码存于二维数组中

2、每次移动时跳一格，但要判断中间是否有墙

3、先独立地求出每一点的最短路径，再遍历每一个点，找最大的“糟糕点”

4、用种子染色法，从两个终点开始搜索，遍历全图，每次根据已知点+1的值更新未知点（松弛的方向（从小到大）决定了它不可能搜索出环来），再递归未知点。

下面是参考代码：

/*ID: linda_f1PROG: maze1LANG: C++*/#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int n,m;//M排，N列 int map[300][300]={
     0};//0 represents free to pass while 1 represents notint maxx=0;int derx[5]={
     0,2,0,-2,0};int dery[5]={
     0,0,2,0,-2};int dfs(int x,int y){ int xx,yy,ax,ay;   for(int i=1;i<=4;i++) {  int flag=0;  xx=x+derx[i];  yy=y+dery[i];  ax=x+derx[i]/2;  ay=y+dery[i]/2;  if(map[ax][ay]!=-1&&map[xx][yy]!=-1&&map[xx][yy]>map[x][y]+1&&xx>=1&&xx<=m&&yy>=1&&yy<=n)  {   map[xx][yy]=map[x][y]+1;//松弛操作   dfs(xx,yy);   } }}int main(){ freopen("maze1.in","r",stdin); freopen("maze1.out","w",stdout); memset(map,31,sizeof(map)); cin>>n>>m; m=m*2+1; n=n*2+1;// int s[6],sum=0;  for(int i=1;i<=m;i++) {  char c;   scanf("%c",&c);//在每行的开始会有一个回车，处理掉它   for(int j=1;j<=n;j++)  {   scanf("%c",&c);   if(c=='+'||c=='-'||c=='|')    map[i][j]=-1;//   if(c==' '&&(i==m||i==1||j==n||j==1))//   {//    s[++sum]=i;//    s[++sum]=j; //   }  } } //下面是寻找那两个出口，并开始搜索  for(int i=1;i<=m;i++) {  if(map[i][1]!=-1)   {   map[i][2]=1;   dfs(i,2);   }  if(map[i][n]!=-1)   {   map[i][n-1]=1;    dfs(i,n-1);  } } for(int i=1;i<=n;i++) {  if(map[1][i]!=-1)   {   map[2][i]=1;   dfs(2,i);   }  if(map[m][i]!=-1)   {   map[m-1][i]=1;    dfs(m-1,i);  } } for(int i=1;i<=m;i++)  for(int j=1;j<=n;j++)  {   if(map[i][j]>maxx&&map[i][j]<10000)    maxx=map[i][j];  } cout<
           
            <