题目1335:闯迷宫(40分)

2020年05月09日 阅读数:105
这篇文章主要向大家介绍题目1335:闯迷宫(40分),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

http://ac.jobdu.com/problem.php?id=1335php


题目描述:

sun所在学校每一年都要举行电脑节,今年电脑节有一个新的趣味比赛项目叫作闯迷宫。
sun的室友在帮电脑节设计迷宫,因此室友就请sun帮忙计算下走出迷宫的最少步数。
知道了最少步数就能够辅助控制比赛难度以及去掉一些没有路径到达终点的map。
比赛规则是:从原点(0,0)开始走到终点(n-1,n-1),只能上下左右4个方向走,只能在给定的矩阵里走。ios

输入:

输入有多组数据。
每组数据输入n(0<n<=100),而后输入n*n的01矩阵,0表明该格子没有障碍,为1表示有障碍物。
注意:若是输入中的原点和终点为1则这个迷宫是不可达的。算法

输出:

对每组输入输出该迷宫的最短步数,若不能到达则输出-1。测试

样例输入:
2
0 1
0 0
5
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
0 1 1 1 0
1 0 1 0 0
样例输出:
2
8
一开始没认真看题目,觉得是最简单的只能向下和向右两个方向走,因而简单的打表递推提交经过了10个测试用例里的4个,看到题目中的是能够向四个方向移动的,既然一开始考虑使用状态转移就坚持一条道走到黑了,这里存在的问题是不知足dp里的无后效性,不太好找到一个合适的方向进行计算,由于当前节点的值会依赖4个相邻的结点,彷佛一趟扫描基本不太可能,不过最近实现一篇论文的时候用到了  fast sweeping算法,具体的思想也是从一些肯定点source的效果逐级扩散到其余点(这里本质上很类似,并且不用记录到达每个状态的细节信息),一开始简单的表递推的时候从四个方向扫描,最后再加上一趟从左上到右下的扫描结果经过10个里面的9个(其实只是随便试一试,明显感受算法在逻辑上仍是有问题的(由于更新的时候始终只考虑两个相邻的两个点),说明测试用例并非太强),如下是代码:     写到后面才发现代码中有致命问题的, 由于下标为0的两列值再初始肯定后就固定了不在更新了,囧

#include <iostream>
#include <iomanip>
#include <cmath>
//#include <map>
#include <assert.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
const int MAXDIST = 10000;
int map[105][105];
int dist[105][105];
void InitDist( int n)
{
     for ( int i=0; i<=n; i++) //多取一位
         for ( int j=0; j<=n; j++)
             dist[i][j]=MAXDIST;
}
int computePath( int n)
{
     if (map[0][0]==1 || map[n-1][n-1]==1)
         return -1;
     InitDist(n);
     dist[0][0]=0;
     for ( int i=1; i<n; i++)
         if (0 == map[0][i])
             dist[0][i]=dist[0][i-1]+1;
     
     for ( int i=1; i<n; i++)
         if (0==map[i][0])
             dist[i][0]=dist[i-1][0]+1;
 
 
     for ( int i=1; i<n; i++)
         for ( int j=1; j<n; j++) //红色部分为问题所在,后面相似
         {
             if (0 == map[i][j])
             {
                 int temp1 = dist[i-1][j]+1;
                 int temp2 = dist[i][j-1]+1;
                 int temp = temp1<temp2 ? temp1:temp2;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }  
         }
 
     for ( int i=1; i<n; i++)
         for ( int j=n-1; j>0; j--)
             if (0 == map[i][j])
             {
                 int temp1 = dist[i-1][j]+1;
                 int temp2 = dist[i][j+1]+1;
                 int temp = temp1<temp2 ? temp1:temp2;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=n-1; i>0; i--)
         for ( int j=1; j<n; j++)
             if (0 == map[i][j])
             {
                 int temp1 = dist[i+1][j]+1;
                 int temp2 = dist[i][j-1]+1;
                 int temp = temp1<temp2 ? temp1:temp2;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=n-1; i>0; i--)
         for ( int j=n-1; j>0; j--)
             if (0 == map[i][j])
             {
                 int temp1 = dist[i+1][j]+1;
                 int temp2 = dist[i][j+1]+1;
                 int temp = temp1<temp2 ? temp1:temp2;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=1; i<n; i++)
         for ( int j=1; j<n; j++)
         {
             if (0 == map[i][j])
             {
                 int temp1 = dist[i-1][j]+1;
                 int temp2 = dist[i][j-1]+1;
                 int temp = temp1<temp2 ? temp1:temp2;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }  
         }
     if (dist[n-1][n-1]>=MAXDIST)
         return -1;
     else
         return dist[n-1][n-1];
}
int main()
{
     //freopen("in.txt","r",stdin);
     int n;
     while (cin>>n)
     {
         for ( int i=0; i<n; i++)
             for ( int j=0; j<n; j++)
                 cin>>map[i][j];
         cout<<computePath(n)<<endl;
     }
     return 0;
}



纠正上面提到的问题果真AC了, 没有第五趟额外的扫描代码经过不了,因此暂时还不肯定代码绝对正确,第五趟是否必定不会再有值更新并没有把握,之后再仔细考虑吧,不事后面写的直到彻底没值更新了才中止扫描(只朝一个方向扫描只为代码简洁,收敛速度会慢一些吧)160ms-》190ms
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <cmath>
//#include <map>
#include <assert.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
  
const int MAXDIST = 10000;
int map[105][105];
int dist[105][105];
void InitDist( int n)
{
     for ( int i=0; i<=n; i++) //多取一位 从0取才有意义
         for ( int j=0; j<=n; j++)
             dist[i][j]=MAXDIST;
}
int SourceForm( int x, int y, int n)
{
     if (x<0 || x>=n || y<0 || y>=n)
         return MAXDIST;
     else
         return dist[x][y];
}
 
int computePath( int n)
{
     if (map[0][0]==1 || map[n-1][n-1]==1)
         return -1;
     InitDist(n);
     dist[0][0]=0;
     
 
     for ( int i=0; i<n; i++)
         for ( int j=0; j<n; j++)
             if (0 == map[i][j])
             {
                 int temp = SourceForm(i-1,j,n)+1;
                 if (SourceForm(i,j-1,n)+1<temp)
                     temp = SourceForm(i,j-1,n)+1;
                 if (SourceForm(i+1,j,n)+1<temp)
                     temp = SourceForm(i+1,j,n)+1;
                 if (SourceForm(i,j+1,n)+1<temp)
                     temp = SourceForm(i,j+1,n)+1;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=0; i<n; i++)
         for ( int j=n-1; j>=0; j--)
             if (0 == map[i][j])
             {
                 int temp = SourceForm(i-1,j,n)+1;
                 if (SourceForm(i,j-1,n)+1<temp)
                     temp = SourceForm(i,j-1,n)+1;
                 if (SourceForm(i+1,j,n)+1<temp)
                     temp = SourceForm(i+1,j,n)+1;
                 if (SourceForm(i,j+1,n)+1<temp)
                     temp = SourceForm(i,j+1,n)+1;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=n-1; i>=0; i--)
         for ( int j=0; j<n; j++)
             if (0 == map[i][j])
             {
                 int temp = SourceForm(i-1,j,n)+1;
                 if (SourceForm(i,j-1,n)+1<temp)
                     temp = SourceForm(i,j-1,n)+1;
                 if (SourceForm(i+1,j,n)+1<temp)
                     temp = SourceForm(i+1,j,n)+1;
                 if (SourceForm(i,j+1,n)+1<temp)
                     temp = SourceForm(i,j+1,n)+1;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=n-1; i>=0; i--)
         for ( int j=n-1; j>=0; j--)
             if (0 == map[i][j])
             {
                 int temp = SourceForm(i-1,j,n)+1;
                 if (SourceForm(i,j-1,n)+1<temp)
                     temp = SourceForm(i,j-1,n)+1;
                 if (SourceForm(i+1,j,n)+1<temp)
                     temp = SourceForm(i+1,j,n)+1;
                 if (SourceForm(i,j+1,n)+1<temp)
                     temp = SourceForm(i,j+1,n)+1;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     for ( int i=0; i<n; i++)
         for ( int j=0; j<n; j++)
             if (0 == map[i][j])
             {
                 int temp = SourceForm(i-1,j,n)+1;
                 if (SourceForm(i,j-1,n)+1<temp)
                     temp = SourceForm(i,j-1,n)+1;
                 if (SourceForm(i+1,j,n)+1<temp)
                     temp = SourceForm(i+1,j,n)+1;
                 if (SourceForm(i,j+1,n)+1<temp)
                     temp = SourceForm(i,j+1,n)+1;
                 if (temp<dist[i][j])
                     dist[i][j]=temp;
             }
 
     if (dist[n-1][n-1]>=MAXDIST)
         return -1;
     else
         return dist[n-1][n-1];
}
 
 
int main()
{
     //freopen("in.txt","r",stdin);
     int n;
     while (cin>>n)
     {
         for ( int i=0; i<n; i++)
             for ( int j=0; j<n; j++)
                 scanf ( "%d" ,&map[i][j]);
                 //cin>>map[i][j];
         cout<<computePath(n)<<endl;
     }
     return 0;
}
/**************************************************************
     Problem: 1335
     User: xjbscut
     Language: C++
     Result: Accepted
     Time:160 ms
     Memory:1600 kb
****************************************************************/









以为传递思想绝对是OK的,使用了一种以为严谨且暴力保证收敛的手段(每次都考虑四个紧邻,把相邻元素是否越界 封装在SourceForm(int x,int y,int n)中很优雅
#include <iostream>
#include <iomanip>
#include <cmath>
//#include <map>
#include <assert.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
  
const int MAXDIST = 10000;
int map[105][105];
int dist[105][105];
void InitDist( int n)
{
     for ( int i=0; i<=n; i++) //多取一位 从0取才有意义
         for ( int j=0; j<=n; j++)
             dist[i][j]=MAXDIST;
}
int SourceForm( int x, int y, int n)
{
     if (x<0 || x>=n || y<0 || y>=n)
         return MAXDIST;
     else
         return dist[x][y];
}
int computePath( int n)
{
     if (map[0][0]==1 || map[n-1][n-1]==1)
         return -1;
     InitDist(n);
     dist[0][0]=0;
     bool hasUpadated;
    
     do
     {
         hasUpadated = false ;
         for ( int i=0; i<n; i++)
             for ( int j=0; j<n; j++)
                 if (0 == map[i][j])
                 {
//考虑四个相邻元素
                     int temp = SourceForm(i-1,j,n)+1;
                     if (SourceForm(i,j-1,n)+1<temp)
                         temp = SourceForm(i,j-1,n)+1;
                     if (SourceForm(i+1,j,n)+1<temp)
                         temp = SourceForm(i+1,j,n)+1;
                     if (SourceForm(i,j+1,n)+1<temp)
                         temp = SourceForm(i,j+1,n)+1;
                     if (temp<dist[i][j])
                     {
                         dist[i][j]=temp;
                         hasUpadated =true;
                     }
                 }
 
     } while (hasUpadated);
 
 
     if (dist[n-1][n-1]>=MAXDIST)
         return -1;
     else
         return dist[n-1][n-1];
}
int main()
{
     //freopen("in.txt","r",stdin);
     int n;
     while (cin>>n)
     {
         for ( int i=0; i<n; i++)
             for ( int j=0; j<n; j++)
                 scanf ( "%d" ,&map[i][j]);
                 //cin>>map[i][j];
         cout<<computePath(n)<<endl;
     }
     return 0;
}
/**************************************************************
     Problem: 1335
     User: xjbscut
     Language: C++
     Result: Accepted
     Time:190 ms
     Memory:1596 kb
****************************************************************/


其实撇开这种递推的思路,使用DFS是这种问题的最直观的思路,可是搜索算法相对来讲比较难写好,特别使得处理好剪枝,不然很容易超时,能够考虑的是搜索的过程当中记录到每个中间点的当前最短消费(而不是只存储目标点的信息,到了目标节点才进行实际的消费比较),这样能够减小大量没必要要的搜索,不过即便这样仍是超时,其中第五个测试样例超过了1s,前面经过的样例都只有20ms左右)估计是一个比较强的测试用例,想了下加了个剪纸就AC了,不过期间在AC结果里面仍是比较长的(480ms)
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <assert.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace