题解：洛谷 P5195 [USACO05DEC] Knights of Ni S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P5195 [USACO05DEC] Knights of Ni S - 洛谷【题目描述】贝茜遇到了一件很麻烦的事她无意中闯入了森林里的一座城堡如果她想回家就必须穿过这片由骑士们守护着的森林。为了能安全地离开贝茜不得不按照骑士们的要求在森林寻找一种特殊的灌木并带一棵给他们。当然贝茜想早点离开这可怕的森林于是她必须尽快完成骑士们给的任务贝茜随身带着这片森林的地图地图上的森林被放入了直角坐标系并按x , y x,yx,y轴上的单位长度划分成了W × H ( 1 ≤ W , H ≤ 1000 ) W \times H\ ( 1 \leq W,H \leq 1000 )W×H(1≤W,H≤1000)块贝茜在地图上查出了她自己以及骑士们所在的位置当然地图上也标注了她所需要的灌木生长的区域。某些区域是不能通过的比如说沼泽地悬崖以及食人兔的聚居地。在没有找到灌木之前贝茜不能通过骑士们所在的那个区域为了确保她自己不会迷路贝茜只向正北、正东、正南、正西四个方向移动注意她不会走对角线。她要走整整一天才能从某块区域走到与它相邻的那块区域。贝茜希望你能帮她计算一下她最少需要多少天才可脱离这可怕的地方输入数据保证贝茜一定能完成骑士的任务。【输入】第一行输入2 22个用空格隔开的整数即题目中提到的W , H W,HW,H。接下来输入贝茜持有的地图每一行用若干个数字代表地图上对应行的地形。第一行描述了地图最北的那一排土地最后一行描述的则是最南面的。相邻的数字所对应的区域是相邻的。如果地图的宽小于或等于40 4040那每一行数字恰好对应了地图上的一排土地。如果地图的宽大于40 4040那每行只会给出40 4040个数字并且保证除了最后一行的每一行都包含恰好40 4040个数字。没有哪一行描述的区域分布在两个不同的行里。地图上的数字所对应的地形0 00贝茜可以通过的空地1 11由于各种原因而不可通行的区域2 22贝茜现在所在的位置3 33骑士们的位置4 44长着贝茜需要的灌木的土地。【输出】输出一个正整数即贝茜最少要花多少天才能完成骑士们给的任务。【输入样例】8 4 4 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 2 1 1 3 0 4 0 0 0 0 4 1 1 1 0【输出样例】11【算法标签】#普及plus #BFS-二维【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;// 定义网格最大尺寸inth,w,ans1e9;// 网格高度h宽度w答案ans初始化为极大值inta[N][N],dist1[N][N],dist2[N][N];// 网格数组a起点距离dist1钥匙距离dist2structNode{intr,c;// 结构体存储坐标}st,ks[N*N],fs[N*N];// 起点st钥匙数组ks食物数组fsintcur1,cur2;// 钥匙数量cur1食物数量cur2boolvis[N][N];// 访问标记数组intdx[4]{-1,1,0,0};// 四个方向的x偏移intdy[4]{0,0,-1,1};// 四个方向的y偏移voidbfs1()// 从起点开始的第一轮广度优先搜索{memset(vis,0,sizeof(vis));// 初始化访问标记为未访问memset(dist1,0x3f,sizeof(dist1));// 初始化起点距离为无穷大queueNodeq;// 广度优先搜索队列q.push(st);// 起点入队dist1[st.r][st.c]0;// 起点到自己的距离为0vis[st.r][st.c]1;// 标记起点为已访问while(!q.empty())// 当队列不为空时循环{intxq.front().r,yq.front().c;// 取出队首坐标q.pop();// 出队for(inti0;i4;i)// 遍历四个方向{intnxxdx[i],nyydy[i];// 计算相邻位置if(nx1||nxh||ny1||nyw||vis[nx][ny]||a[nx][ny]1||a[nx][ny]3)continue;// 检查是否越界、已访问、是墙或是钥匙dist1[nx][ny]dist1[x][y]1;// 更新相邻位置的距离vis[nx][ny]1;// 标记相邻位置为已访问q.push({nx,ny});// 相邻位置入队}}}voidbfs2()// 从所有钥匙开始的第二轮广度优先搜索{memset(vis,0,sizeof(vis));// 初始化访问标记为未访问memset(dist2,0x3f,sizeof(dist2));// 初始化钥匙距离为无穷大queueNodeq;// 广度优先搜索队列for(inti1;icur1;i)// 将所有钥匙加入队列{q.push(ks[i]);// 钥匙入队vis[ks[i].r][ks[i].c]1;// 标记钥匙位置为已访问dist2[ks[i].r][ks[i].c]0;// 钥匙到自己的距离为0}while(!q.empty())// 当队列不为空时循环{intxq.front().r,yq.front().c;// 取出队首坐标q.pop();// 出队for(inti0;i4;i)// 遍历四个方向{intnxxdx[i],nyydy[i];// 计算相邻位置if(nx1||nxh||ny1||nyw||vis[nx][ny]||a[nx][ny]1)continue;// 检查是否越界、已访问、是墙dist2[nx][ny]dist2[x][y]1;// 更新相邻位置的距离vis[nx][ny]1;// 标记相邻位置为已访问q.push({nx,ny});// 相邻位置入队}}}intmain()// 主函数{cinwh;// 输入网格宽度w和高度hfor(inti1;ih;i)// 遍历网格的每一行{for(intj1;jw;j)// 遍历网格的每一列{cina[i][j];// 输入网格单元格的值if(a[i][j]2)// 如果当前单元格是起点{st{i,j};// 记录起点坐标}if(a[i][j]3)// 如果当前单元格是钥匙{ks[cur1]{i,j};// 记录钥匙坐标钥匙数量加1}if(a[i][j]4)// 如果当前单元格是食物{fs[cur2]{i,j};// 记录食物坐标食物数量加1}}}bfs1();// 执行从起点开始的广度优先搜索bfs2();// 执行从所有钥匙开始的广度优先搜索for(inti1;icur2;i)// 遍历所有食物位置{Node tfs[i];// 获取当前食物的坐标ansmin(ans,dist1[t.r][t.c]dist2[t.r][t.c]);// 更新最短路径长度为起点到食物距离加上钥匙到食物距离的最小值}coutansendl;// 输出最短路径长度return0;// 程序正常结束}【运行结果】8 4 4 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 2 1 1 3 0 4 0 0 0 0 4 1 1 1 0 11