اینم به خاطر شما :
سوال : https://www.spoj.pl/problems/CLEANRBT/
جواب :
import java.io.*;
import java.util.*;
public class Main {
static int w[][],num;
static int dp[][];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int m,n;
while(true){
StringTokenizer st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
if(m==0 && n==0) break;
ArrayList<Integer> dirt=new ArrayList<Integer>();
int first=0;
char map[][]=new char[m][n];
for (int i = 0; i < m; i++) {
String s=br.readLine();
for (int j = 0; j < n; j++) {
if((map[i][j]=s.charAt(j))=='o'){
first=n*i+j;
dirt.add(0,first);
}
if(map[i][j]=='*') dirt.add(n*i+j);
}
}
w=new int[10][10];
int move[][]={{1,0},{-1,0},{0,1},{0,-1}};
num=dirt.size();
for (int i = 0; i < num; i++) {
boolean check[][]=new boolean[m][n];
LinkedList<Integer> q=new LinkedList<Integer>();
int pop=dirt.get(i),x=pop/n,y=pop%n,L=0;
q.add(pop);
check[x][y]=true;
while(!q.isEmpty()){
int l=q.size();
for (int k = 0; k < l; k++) {
pop=q.removeFirst();
x=pop/n; y=pop%n;
if(map[x][y]=='*' || map[x][y]=='o')
w[i][dirt.indexOf(n*x+y)]=L;
for (int j = 0; j < 4; j++) {
int X=x+move[j][0],Y=y+move[j][1];
if(X==-1 || X==m || Y==-1 || Y==n || check[X][Y] || map[x][y]=='x') continue;
q.add(n*X+Y);
check[X][Y]=true;
}
}
L++;
}
}
boolean bad=false;
for (int i = 0; i < num; i++) {
for (int j = i+1; j < num; j++) {
if(w[i][j]==0) bad=true;
}
}
if(bad){
System.out.println(-1);
continue;
}
dp=new int[num][1<<num];
for (int i = 0; i < num; i++) {
Arrays.fill(dp[i], -1);
}
System.out.println(f(0,(1<<num)-1));
}
}
static int f(int i,int j){
if(dp[i][j]!=-1) return dp[i][j];
if(j==1) return 0;
int min=100000;
for (int k = 1; k < num; k++) {
if((j&(1<<k))!=0)
min=Math.min(min, w[i][k]+f(k,j-(1<<k)));
}
return dp[i][j]=min;
}
}