迷宫
题目描述
给定一个迷宫，迷宫中有一些障碍和一些记录点，你需要在不经过障碍的情况下，按顺序依次经过每个记录点（不能提前经过），若有解则求出最小的步数，否则输出\(-1\)。
输入格式：
第一行三个整数\(N\)，\(M\)，\(K\)，表示迷宫的大小为\(N*M\),有\(K\)个记录点。
接下来\(N\)行每行\(M\)个整数（\(0\)表示空地，\(1\)表示障碍）,表示迷宫的布局。
接下来\(K\)行每行两个整数\(x\)，\(y\)，表示记录点在第\(x\)行第\(y\)列，记录点需要按输入顺序依次经过（记录点保证不在障碍格子，没有记录点在同一格子），已经过的记录点不能再次经过。
接下来一行是两个整数\(x_0\),\(y_0\)，表示起始位置（保证不在障碍格子）。
输出格式：
共一行，一个整数\(ans\)，表示最小的步数或无解。
样例输入：
3 3 2 0 0 0 0 1 0 0 0 0 3 3 3 1 1 1
样例输出：
6
数据范围：
对于\(10%\)的数据，\(N,M<=4\)，\(K<=1\)。
对于\(30%\)的数据，\(N,M<=10\)。
对于\(60%\)的数据，\(N,M<=100\)。
对于\(100%\)的数据，\(N,M<=1000\)，\(K<=10\)。
时间限制：
1S
空间限制：
512M
提示：
remove!!!
题解
题目要求从起点依次经过一些点的最短路，而且走过的点不能再走。
那么我们把最短路分成多次求最短路，把不能经过的点在原图上加1，跑完后再减去就行了。
这里我用spfa求最短路。
上代码：（突然发现我程序的命名好不规范，各位将就看看吧）
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[1009][1009];
int dis[1009][1009],ans;
struct aa{
int x,y;
}p[19];
int xx,yy;
aa pp[1000009];
int l,r;
int ds[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y,int tx,int ty){
memset(dis,-1,sizeof(dis));
dis[x][y]=0;l=r=1;
pp[1].x=x;pp[1].y=y;
while(l<=r){
int ux=pp[l].x,uy=pp[l++].y;
for(int j=0;j<4;j++){
int ttx=ux+ds[j][0],tty=uy+ds[j][1];
if(ttx<1 || tty<1 || ttx>n || tty>m || a[ttx][tty]>0) continue;
if(dis[ttx][tty]==-1 || dis[ttx][tty]>dis[ux][uy]+1){
dis[ttx][tty]=dis[ux][uy]+1;
pp[++r].x=ttx;
pp[r].y=tty;
}
}
if(dis[tx][ty]!=-1) return;
}
}
void df(int x){
for(int j=1;j<=k;j++)
if(j!=x) a[p[j].x][p[j].y]++;
}
void ddf(int x){
for(int j=1;j<=k;j++)
if(j!=x) a[p[j].x][p[j].y]--;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int j=1;j<=n;j++){
for(int i=1;i<=m;i++)
scanf("%d",&a[j][i]);
}
for(int j=1;j<=k;j++)
scanf("%d%d",&p[j].x,&p[j].y);
scanf("%d%d",&xx,&yy);
df(1);
dfs(xx,yy,p[1].x,p[1].y);
ddf(1);
if(dis[p[1].x][p[1].y]==-1){
printf("-1");
return 0;
}
ans+=dis[p[1].x][p[1].y];
for(int j=2;j<=k;j++){
df(j);
dfs(p[j-1].x,p[j-1].y,p[j].x,p[j].y);
ddf(j);
if(dis[p[j].x][p[j].y]==-1){
printf("-1");
return 0;
}
ans+=dis[p[j].x][p[j].y];
}
printf("%d",ans);
return 0;
}