Problem:


Problem G: Building Water Ways

In ancient times, Romans constructed numerous water ways to supply water to cities and industrial sites. These water ways were amongst the greatest engineering feats of the ancient world.

These water ways contributed to social infrastructures which improved people's quality of life. On the other hand, problems related to the water control and the water facilities are still interesting as a lot of games of water ways construction have been developed.

Your task is to write a program which reads a map and computes the minimum possible cost of constructing water ways from sources to all the cities.

As shown in Figure 1, the map is represented by H &times W grid cells, where each cell represents source, city, flatland, or obstacle.

You can construct only one water way from a source, but there are no limitations on the length of that water way and it can provide water to any number of cities located on its path. You can not construct water ways on the obstacles.

Your objective is to bring water to all the city and minimize the number of cells which represent water ways. In the Figure 1, water ways are constructed in 14 cells which is the minimum cost.

The water ways must satisfy the following conditions:

a water way cell is adjacent to at most 2 water way cells in four cardinal points.

a source cell is adjacent to at most 1 water way cell in four cardinal points.

there is no path from a source to other sources through water ways.

Input

The input consists of multiple datasets. Each dataset consists of:

H W
H &times; W characters

The integers H and W are the numbers of rows and columns of the map. H &times; W characters denote the cells which contain:

'P': source

'*': city

'.': flatland

'#': obstacle

The end of input is indicated by a line containing two zeros separated by a space.

Output

For each dataset, print the minimum cost to construct the water ways.

Constraints

Judge data contains at most 60 data sets.

3 ≤ H, W ≤ 10

1 ≤ the number of sources, the number of cities ≤ 8

The map is surrounded by obstacles.

Sources are not adjacent each other(on the left, right, top and bottom)

There is a solution.

Sample Input

3 8
########
#P....*#
########
10 10
##########
#P.......#
#..#*....#
#..#*.#.*#
#.....#*.#
#*.......#
#..##....#
#...#.P..#
#P......P#
##########
0 0

Output for the Sample Input

5
14



Sample input:
3 8
########
#P....*#
########
10 10
##########
#P.......#
#..#*....#
#..#*.#.*#
#.....#*.#
#*.......#
#..##....#
#...#.P..#
#P......P#
##########
0 0


Sample output:
5
14

Submission status: Wrong Answer

Solution code:
code="""\
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

constexpr int di[]={-1,1,0,0},dj[]={0,0,-1,1};

int count(const vs& grid,int i,int j)
{
	int cnt=0;
	rep(k,4){
		int ni=i+di[k],nj=j+dj[k];
		cnt+=grid[ni][nj]=='P' || grid[ni][nj]=='W' || grid[ni][nj]=='C';
	}
	return cnt;
}

void print(const vs& grid)
{
	cout<<"# grid:"<<endl;
	for(const auto& line:grid) cout<<line<<endl;
}

int solve(vs& grid,int i,int j,const vector<pii>& ps,int pi,int rest)
{
	int h=grid.size(),w=grid[0].size();
	if(grid[i][j]=='#' || (grid[i][j]=='P')+count(grid,i,j)>=2) return INF;
	if(grid[i][j]=='*'){
		rest--;
		grid[i][j]='C';
		int res=INF;
		if(rest==0){
			res=0;
			rep(i,h) rep(j,w) res+=grid[i][j]=='W' || grid[i][j]=='C';
		}
		else{
			rep(k,4){
				int ni=i+di[k],nj=j+dj[k];
				res=min(res,solve(grid,ni,nj,ps,pi,rest));
			}
			if(pi+1<ps.size()){
				int ni,nj; tie(ni,nj)=ps[pi+1];
				res=min(res,solve(grid,ni,nj,ps,pi+1,rest));
			}
		}
		grid[i][j]='*';
		return res;
	}
	else{
		if(grid[i][j]!='P') grid[i][j]='W';
		int res=INF;
		rep(k,4){
			int ni=i+di[k],nj=j+dj[k];
			res=min(res,solve(grid,ni,nj,ps,pi,rest));
		}
		if(grid[i][j]!='P') grid[i][j]='.';
		return res;
	}
	return 0;
}

int main()
{
	for(int h,w;cin>>h>>w && h|w;){
		vs grid(h);
		rep(i,h) cin>>grid[i];
		
		vector<pii> ps;
		rep(i,h) rep(j,w) if(grid[i][j]=='P') ps.emplace_back(i,j);
		
		int i0,j0; tie(i0,j0)=ps[0];
		int rest=0; rep(i,h) rep(j,w) rest+=grid[i][j]=='*';
		cout<<solve(grid,i0,j0,ps,0,rest)<<endl;
	}
}
"""

import os,tempfile
(_,filename)=tempfile.mkstemp(".cpp")

f=open(filename,"w")
f.write(code)
f.close()

os.system("g++ -std=c++0x -O2 {}".format(filename))
os.system("./a.out")

Submission status: Runtime Error

Solution code:
code="""\
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

constexpr int di[]={-1,1,0,0},dj[]={0,0,-1,1};

int count(const vs& grid,int i,int j)
{
	int cnt=0;
	rep(k,4){
		int ni=i+di[k],nj=j+dj[k];
		cnt+=grid[ni][nj]=='P' || grid[ni][nj]=='W' || grid[ni][nj]=='C';
	}
	return cnt;
}

void print(const vs& grid)
{
	cout<<"# grid:"<<endl;
	for(const auto& line:grid) cout<<line<<endl;
}

int solve(vs& grid,int i,int j,const vector<pii>& ps,int pi,int rest)
{
	int h=grid.size(),w=grid[0].size();
	if(grid[i][j]=='#' || (grid[i][j]=='P')+count(grid,i,j)>=2) return INF;
	if(grid[i][j]=='*'){
		rest--;
		grid[i][j]='C';
		int res=INF;
		if(rest==0){
			res=0;
			rep(i,h) rep(j,w) res+=grid[i][j]=='W' || grid[i][j]=='C';
		}
		else{
			rep(k,4){
				int ni=i+di[k],nj=j+dj[k];
				res=min(res,solve(grid,ni,nj,ps,pi,rest));
			}
			if(pi+1<ps.size()){
				int ni,nj; tie(ni,nj)=ps[pi+1];
				res=min(res,solve(grid,ni,nj,ps,pi+1,rest));
			}
		}
		grid[i][j]='*';
		return res;
	}
	else{
		if(grid[i][j]!='P') grid[i][j]='W';
		int res=INF;
		rep(k,4){
			int ni=i+di[k],nj=j+dj[k];
			res=min(res,solve(grid,ni,nj,ps,pi,rest));
		}
		if(grid[i][j]!='P') grid[i][j]='.';
		return res;
	}
	return 0;
}

int main()
{
	for(int h,w;cin>>h>>w && h|w;){
		vs grid(h);
		rep(i,h) cin>>grid[i];
		
		vector<pii> ps;
		rep(i,h) rep(j,w) if(grid[i][j]=='P') ps.emplace_back(i,j);
		
		int i0,j0; tie(i0,j0)=ps[0];
		int rest=0; rep(i,h) rep(j,w) rest+=grid[i][j]=='*';
		cout<<solve(grid,i0,j0,ps,0,rest)<<endl;
	}
}
"""

import os,tempfile
(_,filename)=tempfile.mkstemp(".cpp")

f=open(filename,"w")
f.write(code)
f.close()

os.system("g++ -std=c++0x -O2 {}".format(filename))
#os.system("./a.out")
os.system("a.exe")