Codeforces Div 1 C Three States Solution in Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Threestate {
static int n;
static int m;
static char map[][];
static int dis[][][];
static class Cord implements Comparable<Cord>
{
int x;
int y;
int d;
Cord(int x,int y,int d)
{
this.x=x;
this.y=y;
this.d=d;
}
public int compareTo(Cord b)
{
return d-b.d;
}
}
public static void main(String[] args)
{
// TODO Auto-generated method stub
MyScannerthreestate sc=new MyScannerthreestate();
n=sc.nextInt();
m=sc.nextInt();
map=new char[n+2][m+2];
dis=new int[4][n+2][m+2];
int i,j,k;
for(i=1;i<=n;i++)
{
String scr=sc.next();
System.arraycopy(scr.toCharArray(),0, map[i],1,m);
}
for(i=0;i<=3;i++)
{
for(j=0;j<n+2;j++)
{
Arrays.fill(dis[i][j],Integer.MAX_VALUE/3);
}
}
for(i=1;i<=3;i++)
{
bfs(i);
}
int min=Integer.MAX_VALUE;
int ix=0;int iy=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(map[i][j]=='#')
continue;
int v=0;
for(k=1;k<=3;k++)
{
v+=dis[k][i][j];
}
if(map[i][j]=='.')
v-=2;
if(min>v)
{
min=v;
}
}
}
System.out.println(min>=Integer.MAX_VALUE/3?-1:min);
}
static void bfs(int num)
{
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
PriorityQueue<Cord> q=new PriorityQueue<Cord>();
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(map[i][j]=='#')
continue;
for(k=0;k<4;k++)
{
int x=i+dx[k];
int y=j+dy[k];
if(map[x][y]=='0'+num)
break;
}
if(k<4)
{
int cnt=(map[i][j]=='.'?1:0);
dis[num][i][j]=cnt;
q.add(new Cord(i,j,cnt));
}
}
}
while(!q.isEmpty())
{
Cord c=q.poll();
for(i=0;i<4;i++)
{
int nx=c.x+dx[i];
int ny=c.y+dy[i];
int cnt=c.d+(map[nx][ny]=='.'?1:0);
if(validate(nx,ny) && dis[num][nx][ny]>cnt)
{
if(map[nx][ny]=='#')
continue;
dis[num][nx][ny]=cnt;
q.add(new Cord(nx,ny,cnt));
}
}
}
}
static boolean validate(int x,int y)
{
if(x>=1 && x<=n && y>=1 && y<=m )
return true;
return false;
}
}
class MyScannerthreestate
{
BufferedReader br;
StringTokenizer st;
MyScannerthreestate()
{
br=new BufferedReader(new InputStreamReader(System.in));
}
String next()
{
while(st==null || !st.hasMoreTokens())
{
try
{
st=new StringTokenizer(br.readLine());
}
catch(Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str="";
try
{
str=br.readLine();
}
catch(Exception e)
{
e.printStackTrace();
}
return str;
}
}
Comments
Post a Comment