题意
样例输入:
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。
解析
多轮bfs,每轮统计当前这轮的最短步数。
类似时间戳。
每轮可以走当前这个点,其他的记录点不能走
代码
//std
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int x[15],y[15],sx,sy,ex,ey,n,m,k;
int g[N][N],d[N][N],vis[N][N],ans;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
struct node{
int x,y,step;
};
int bfs(int time){
queue<node> q;
vis[sx][sy] = time;
q.push({sx,sy,0});
while(q.size()){
node now = q.front();
q.pop();
if(now.x == ex && now.y == ey){
return now.step;
}
for(int i = 0; i < 4; i ++ ){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
if(g[nx][ny] == 1) continue;
if(d[nx][ny] == 1) continue;
if(vis[nx][ny] == time) continue;
vis[nx][ny] = time;
q.push({nx,ny,now.step + 1});
}
}
return -1;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
scanf("%d",&g[i][j]);
}
}
//先要把所有点存下来 才能知道有没有经过后面的记录点
for(int i = 1; i <= k; i ++ ){
scanf("%d %d",&x[i],&y[i]);
d[x[i]][y[i]] = 1;
}
scanf("%d %d",&sx,&sy);
for(int i = 1; i <= k; i ++ ){
//每次当前这个点可以走 别的记录点不能走
d[x[i]][y[i]] = 0;
ex = x[i],ey = y[i];
int tmp = bfs(i);
if(tmp >= 0){
ans += tmp;//总步数 加上 当前走的步数
}else{
//某次到不了某个点 就结束
cout << - 1;
return 0;
}
sx = x[i],sy = y[i];
d[x[i]][y[i]] = 1;
}
cout << ans;
return 0;
}
标签:ny,int,迷宫,nx,vis,continue,now
From: https://www.cnblogs.com/dtdbm/p/17252285.html