Problem Description: You start at a point (sx,sy). There are T gravestones at on the map. You can destroy(diss joy?) a gravestone by touch the four sides that are adjacent to it. After destroying a gravestone, the gravestone turns into a wall, which you cannot pass through. As a Übermensch, you can move in one direction with infinite speed. However, turning takes one amount of time. Please output the minimum amount of time you are going to take in order to break all of the gravestones.
Input Format:
The first line contains three integer N,M ≤ 50,T ≤ 15 represents rows, columns and the number of gravestons.
The next N lines each contains M characters. ‘.’ represents empty space and ‘#’ represents a gravestone.
The next T lines each contains two numbers represents the position of the gravestone in the above graph.
The last line contains two integers representing the position where you are at initially.
Output Format:
One line with the minimum number of steps needed.
Sample Input:
>4 6 3
……
….#.
…..#
….#.
2 5
3 6
4 5
1 5
Sample Output:
5
Solution: Emm.. This one takes me a long time to figure out. Didn’t figure it out myself. First of all, from the constraint on T, we can guess that this is a DP problem using binary mask. By further deduction, we found that the order of choosing matters, we want to focus on the set that is selected. Therefore, we can use BFS/SPFA to pre-compute the shortest path/time between the points adjacent to the gravestones and start to DP. We define f[i][x] as the minimum time selecting set i and having number x as the last selected point, then we have the following equation.
$$f[i][x] = \min_{j\in{i},(1<<(y - 1)) | j == i,x,y\in\textbf{T}}(f[j][x] + cost[x][y] + 1)$$$
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
inline int get_pt(int i,int dir){
return (i – 1) * 4 + dir + 1;
}
#define inf 0x7f7f7f7f
int N,M,T;
int f[1<<20][100],dis[105][105][4],cost[100][100],inq[105][105];
char mpp[105][105];
pii pos[20];
struct node{
int x,y;
node(int a = 0,int b = 0,int d = 0):x(a),y(b){}
};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
queue<node> q;
void bfs(int sx,int sy,int id){
if(mpp[sx][sy] == ‘#’ || sx < 1 || sx > N || sy < 1 || sy > M) return;
memset(dis,0x7f,sizeof(dis));
for(int i = 0; i < 4; i++) dis[sx][sy][i] = 0;
q.push(node(sx,sy));
inq[sx][sy] = 1;
while(!q.empty()){
node now = q.front(); q.pop();
int x = now.x, y = now.y;
for(int i = 0; i < 4; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(mpp[tx][ty] == ‘#’ || tx < 1 || tx > N || ty < 1 || ty > M) continue;
for(int j = 0; j < 4; j++){
if(dis[tx][ty][j] > dis[x][y][i] + (i != j)){
dis[tx][ty][j] = dis[x][y][i] + (i != j);
if(!inq[tx][ty]){
inq[tx][ty] = 1;
q.push(node(tx,ty));
}
}
}
}
inq[x][y] = 0;
}
for(int i = 1; i <= T; i++){
for(int k = 0; k < 4; k++){
int st = inf;
int tx = pos[i].first + dx[k],ty = pos[i].second + dy[k];
for(int j = 0; j < 4; j++){
st = min(st,dis[tx][ty][j] + (tx + dx[j] != pos[i].first || ty + dy[j] != pos[i].second));
}
cost[id][get_pt(i,k)] = st;
}
}
}
int main(){
cin>>N>>M>>T;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin>>mpp[i][j];
}
}
for(int i = 1; i <= T; i++) cin>>pos[i].first>>pos[i].second;
cin>>pos[0].first>>pos[0].second;
memset(cost,0x7f,sizeof(cost));
for(int i = 1; i <= T; i++){
for(int j = 0; j < 4; j++) bfs(pos[i].first + dx[j],pos[i].second + dy[j],get_pt(i,j));
}
bfs(pos[0].first,pos[0].second,4 * T + 1);
memset(f,0x7f,sizeof(f));
f[0][4 * T + 1] = 0;
for(int i = 0; i <= (1 << T) – 1; i++){
for(int x = 1; x <= 4 * T + 1; x++){
if(f[i][x] != inf){
for(int y = 1; y <= 4 * T; y++){
int t = i | (1 << ((y – 1) / 4));
f[t][y] = min(f[t][y], f[i][x] + cost[x][y] + 1);
}
}
}
}
int ans = inf;
for(int i = 1; i <= 4 * T; i++) ans = min(ans,f[(1<<T)-1][i]);
cout<<ans<<endl;
return 0;
}