时间：0.2s 空间：64M
【题目描述】
在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角（1，1），白精灵住在矩阵方格的右下角方格里（N，M）。
在这个矩阵方格例还有一对可穿越的们，这对穿越门的位置不固定，位置可变换（穿越门不会出现在矩阵方格左上角和右下角位置，也不会重叠出现，有且只有一对）。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。
如下图所示：
黑精灵
穿越门
穿越门 白精灵
一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：
1.每次只能走一个方格，可以向上、向下、向左、向右行走；
2.每走一个方格记为一步，但从一扇门穿越到另一扇门穿越门不记步数（从方格走到穿越门和从穿越门到其他方格都计1步）；
3.可借助穿越门去白精灵家（可减少行走步数）。
为了尽快到达白精灵家，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。
例如：
给出一个3*4的矩阵方格，并给出第一个穿越门的坐标位置N1，M1（2，3），第二个穿越门的坐标位置N2，M2（3，1），已知黑精灵初始坐标位置左上角（1，1），白精灵坐标位置右下角（N，M）。
假设用两个大写字母“D”表示矩阵方格中穿越门的位置，1代表黑精灵，2代表白精灵，用数字0表示剩余矩阵方格。
如下图所示：
Wftof7UnicAAAAASUVORK5CYII=
按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。
路线：从黑精灵初始位置（1，1）到正下方方格（2，1）走1步，正下方方格（2，1）到其下方穿越们（3，1）“D”走1步，然后穿越到另一扇穿越门（2，3）向正下方（3，3）走1步，最后到大白精灵家（3，4）需要走1步，故最短路线需要4步。
【输入描述】
第一行输入两个以一个空格隔开的正整数 N(2<N<101), M(2<M<101)，分别表示N行M列的方格矩阵。
接下来第二行输入两个以一个空格隔开的正整数：N1(N1<=N)，M1(M1<=M)，代表第一个穿越门位于第N1行第M1列；
接下来第三行输入两个以一个空格隔开的正整数：N2(N2<=N)，M2(M2<=M)，代表第二个穿越门位于第N2行第M2列；
注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2；两个穿越门位置也不能位于左上角（1，1）和右下角（M，N）；第一个穿越门位置要在第二个穿越门前边或者上边。
【输出描述】
输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。
【样例输入】
3 4
2 3
3 1
【样例输出】
4
1 个赞
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m;
ll bn,bm;
ll en,em;
ll cnt=INT_MAX;
bool vis[102][102];
ll dir[5]={0,1,0,-1,0};
void dfs(ll x,ll y,ll step)
{
if(x==n&&y==m)
{
cnt=min(step-1,cnt);
return ;
}
for(ll i=0;i<4;i++)
{
ll xx=x+dir[i],yy=y+dir[i+1];
if(xx<1||yy<1||xx>n||yy>m)
{
return ;
}
if(vis[xx][yy]==1)
{
return ;
}
if(xx==bn&&yy==bm)
{
xx=en;
yy=em;
step-=1;
}
else if(xx==en&&yy==em)
{
xx=bn;
yy=bm;
step-=1;
}
vis[xx][yy]=1;
dfs(xx,yy,step+1);
vis[xx][yy]=0;
}
}
int main()
{
scanf("%lld%lld",&n,&m);
scanf("%lld%lld",&bn,&bm);
scanf("%lld%lld",&en,&em);
memset(vis,0,sizeof vis);
dfs(1,1,0);
printf("%lld",cnt);
return 0;
}
代码如图
1 个赞
第六题：黑精灵与白精灵
时间：0.2s 空间：64M
【题目描述】
在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角（1，1），白精灵住在矩阵方格的右下角方格里（N，M）。
在这个矩阵方格例还有一对可穿越的们，这对穿越门的位置不固定，位置可变换（穿越门不会出现在矩阵方格左上角和右下角位置，也不会重叠出现，有且只有一对）。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。
一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：
1.每次只能走一个方格，可以向上、向下、向左、向右行走；
2.每走一个方格记为一步，但从一扇门穿越到另一扇门穿越门不记步数（从方格走到穿越门和从穿越门到其他方格都计1步）；
3.可借助穿越门去白精灵家（可减少行走步数）。
为了尽快到达白精灵家，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。
例如：
给出一个3*4的矩阵方格，并给出第一个穿越门的坐标位置N1，M1（2，3），第二个穿越门的坐标位置N2，M2（3，1），已知黑精灵初始坐标位置左上角（1，1），白精灵坐标位置右下角（N，M）。
假设用两个大写字母“D”表示矩阵方格中穿越门的位置，1代表黑精灵，2代表白精灵，用数字0表示剩余矩阵方格。
如下图所示：
按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。
路线：从黑精灵初始位置（1，1）到正下方方格（2，1）走1步，正下方方格（2，1）到其下方穿越们（3，1）“D”走1步，然后穿越到另一扇穿越门（2，3）向正下方（3，3）走1步，最后到大白精灵家（3，4）需要走1步，故最短路线需要4步。
【输入描述】
第一行输入两个以一个空格隔开的正整数 N(2<N<101), M(2<M<101)，分别表示N行M列的方格矩阵。
接下来第二行输入两个以一个空格隔开的正整数：N1(N1<=N)，M1(M1<=M)，代表第一个穿越门位于第N1行第M1列；
接下来第三行输入两个以一个空格隔开的正整数：N2(N2<=N)，M2(M2<=M)，代表第二个穿越门位于第N2行第M2列；
注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2；两个穿越门位置也不能位于左上角（1，1）和右下角（M，N）；第一个穿越门位置要在第二个穿越门前边或者上边。
【输出描述】
输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。
【样例输入】
3 4
2 3
3 1
【样例输出】
4
看似是BFS，实际是曼哈顿（急
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
int n1, m1;
int n2, m2;
int x, y;
cin >> n >> m;
cin >> n1 >> m1;
cin >> n2 >> m2;
// (1, 1) -> (n1, m1) + (n2, m2) -> (n, m)
x = (n1 - 1) + (m1 - 1) + (n - n2) + (m - m2);
// (1, 1) -> (n2, m2) + (n1, m1) -> (n, m)
y = (n2 - 1) + (m2 - 1) + (n - n1) + (m - m1);
cout << min(x, y) << endl;
return 0;
}
有用的话就给个解决方案和赞吧 
3 个赞