Aizu - 0558-Cheese-BFS
发布日期:2022-02-10 08:11:09
浏览次数:18
分类:技术文章
本文共 2140 字,大约阅读时间需要 7 分钟。
Cheese
チーズ () 問題 今年も JOI 町のチーズ工場がチーズの生産を始め,ねずみが巣から顔を出した.JOI 町は東西南北に区画整理されていて,各区画は巣,チーズ工場,障害物,空き地のいずれかである.ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる. この町には,N 個のチーズ工場があり,どの工場も1種類のチーズだけを生産している.チーズの硬さは工場によって異なっており,硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある. ねずみの最初の体力は 1 であり,チーズを 1 個食べるごとに体力が 1 増える.ただし,ねずみは自分の体力よりも硬いチーズを食べることはできない. ねずみは,東西南北に隣り合う区画に 1 分で移動することができるが,障害物の区画には入ることができない.チーズ工場をチーズを食べずに通り過ぎることもできる.すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け.ただし,ねずみがチーズを食べるのにかかる時間は無視できる. 入力 入力は H+1 行ある.1 行目には 3 つの整数 H,W,N (1 ≤ H ≤ 1000,1 ≤ W ≤ 1000,1 ≤ N ≤ 9) がこの順に空白で区切られて書かれている.2 行目から H+1 行目までの各行には,‘S’,‘1’, ‘2’, …, ‘9’,‘X’,’.’ からなる W 文字の文字列が書かれており,各々が各区画の状態を表している.北から i 番目,西から j 番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ H, 1 ≤ j ≤ W),第 i+1 行目の j 番目の文字は,区画 (i,j) が巣である場合は ‘S’ となり,障害物である場合は ‘X’ となり,空き地である場合は ‘.’ となり,硬さ 1, 2, …, 9 のチーズを生産する工場である場合はそれぞれ ‘1’, ‘2’, …, ‘9’ となる.入力には巣と硬さ 1, 2, …, N のチーズを生産する工場がそれぞれ 1 つずつある.他のマスは障害物または空き地であることが保証されている.ねずみは全てのチーズを食べられることが保証されている. 出力 すべてのチーズを食べ終えるまでにかかる最短時間(分)を表す整数を 1 行で出力せよ. 入出力例 入力例 1 3 3 1 S… … …1 出力例 1 4 入力例 2 4 5 2 .X…1 …X .XX.S .2.X. 出力例 2 12 入力例 3 10 10 9 .X…X.S.X 6…5X…X1X …XXXX…X X…9X…X. 8.X2X…X3X …XX.X4… XX…7X… X…X…XX… X…X.XX… …X… 出力例 3 91 問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。题意:从S出发依次走过1,2,…n,输出最小步数
解题思路:用队列保存坐标,BFS求最小步数AC代码:#include#include #include #include #include #define maxn 1005using namespace std;int h,w,n,nx,ny;int dx[]= {0,0,1,-1},dy[]= {1,-1,0,0};struct M{ int a,b,c; //该点的横纵坐标和步数};int main(){ cin>>h>>w>>n; string s[maxn]; M fang[10]; for(int i=0; i >s[i]; int x,y; for(int i=0; i ='1'&&s[i][j]<='9') { fang[s[i][j]-'0'].a=i; fang[s[i][j]-'0'].b=j; fang[s[i][j]-'0'].c=0; } if(s[i][j]=='S') x=i,y=j; } } int jk=1,sumk=0,vis[maxn][maxn]; //jk为第jk个奶酪,sumk为总步数,vis为标记数组 queue que; while(jk<=n) { que.push(M{x,y,sumk}); memset(vis,0,sizeof(vis)); //每找到一个奶酪就需要清空标记数组,因为可能会走同一个地方多次 vis[x][y]=1; while(!que.empty()) { M k=que.front(); if(k.a==fang[jk].a&&k.b==fang[jk].b) { x=fang[jk].a,y=fang[jk].b,sumk=k.c; break; } que.pop(); for(int i=0; i<4; i++) { nx=k.a+dx[i],ny=k.b+dy[i]; if(nx>=0&&nx =0&&ny
转载地址:https://blog.csdn.net/qq_44632981/article/details/98047469 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月14日 00时21分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
xLua(六)——C#访问Lua的function
2019-04-27
基础知识——常用单位介绍
2019-04-27
xLua(七)——Lua访问C#(一)
2019-04-27
xLua(八)——Lua访问C#(二)
2019-04-27
Unity中实现解析Json文件
2019-04-27
Unity自带Json解析库——JsonUtility
2019-04-27
Unity中使用ViedoPlayer操作视频文件
2019-04-27
C#中的的输入与输出
2021-06-30
C#中@符号的作用
2021-06-30
C#中$符号的作用
2021-06-30
Mac装windows系统后如何更换触控板设置
2021-06-30
Windows系统下如何设置软件的快捷键
2021-06-30
语言中的溢出
2021-06-30
Unity中实现获取一段时间内移动设备声音的最大音量
2021-06-30
springboot的初始化启动过程
2021-06-30
关于spring bean 生命周期代码详解-产生到消亡
2021-06-30
spring 启动之全过程 源码解析
2021-06-30
Spring AOP 原理
2021-06-30
mysql 分库分表分区 动态扩容 总结
2021-06-30