# 题目1335：闯迷宫（40分）

2020年05月09日 阅读数：207

sun所在学校每一年都要举行电脑节，今年电脑节有一个新的趣味比赛项目叫作闯迷宫。
sun的室友在帮电脑节设计迷宫，因此室友就请sun帮忙计算下走出迷宫的最少步数。

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

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

#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
****************************************************************/

#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;

do
{
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:190 ms
Memory:1596 kb
****************************************************************/

#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