0558-Cheese
問題概要
日本語なので略
解法
N回BFSを行なう
実装(Java)
import java.util.*; public class Main { Scanner cin; class State{ int time,x,y; State(int time,int x,int y){ this.time=time; this.x=x; this.y=y; } } void run(){ cin=new Scanner(System.in); int H=cin.nextInt(),W=cin.nextInt(),N=cin.nextInt(); String[] MAP=new String[H]; int []dx={1,0,-1,0},dy={0,1,0,-1}; int result=0; for(int i=0;i<H;i++)MAP[i]=cin.next().replaceAll("S","0"); for(int i=0;i<N;i++){ int sx=-1,sy=-1; Queue<State> que=new LinkedList<State>(); Boolean[][] visited=new Boolean[H][W]; for(int p=0;p<H;p++){ for(int q=0;q<W;q++){ visited[p][q]=false; if(MAP[p].charAt(q)==i+'0'){ sx=q;sy=p; } } } que.add(new State(0,sx,sy)); while(!que.isEmpty()){ State now=que.poll(); if(MAP[now.y].charAt(now.x)==i+1+'0'){ result+=now.time; break; } for(int k=0;k<4;k++){ int nx=now.x+dx[k],ny=now.y+dy[k]; if(nx>=0&&nx<W&&ny>=0&&ny<H){ if(visited[ny][nx]==false&&MAP[ny].charAt(nx)!='X'){ visited[ny][nx]=true; que.add(new State(now.time+1,nx,ny)); } } } } } printf("%d\n",result); } void printf(String format,Object... args){ System.out.printf(format, args); } public static void main(String[] args) { new Main().run(); } }