Cerinta completa
The travelling salesman has a map containing m*n squares. He starts from the top left corner and visits every cell exactly once and returns to his initial position (top left). The time taken for the salesman to move from a square to its neighbor might not be the same. Two squares are considered adjacent if they share a common edge and the time taken to reach square b from square a and vice-versa are the same. Can you figure out the shortest time in which the salesman can visit every cell and get back to his initial position?
Input Format
The first line of the input is 2 integers m and n separated by a single space. m and n are the number of rows and columns of the map.
Then m lines follow, each of which contains (n – 1) space separated integers. The jth integer of the ith line is the travel time from position (i,j) to (i,j+1) (index starts from 1.)
Then (m-1) lines follow, each of which contains n space integers. The jth integer of the ith line is the travel time from position (i,j) to (i + 1, j).
Constraints
1 ≤ m, n ≤ 10
Times are non-negative integers no larger than 10000.
Output Format
Just an integer contains the minimal time to complete his task. Print 0 if its not possible to visit each cell exactly once.
Sample Input
2 2
5
8
6 7
Sample Output
26
Explanation
As its a 2*2 square, all cells are visited. 5 + 7 + 8 + 6 = 26
Limbajul de programare folosit: cpp14
Cod:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <ctime>
using namespace std;
typedef long long ll;
class DisjointSet{
public:
DisjointSet( int size ){
rank.resize( size, 0 );
p.resize( size, -1 );
elem.resize( size, 0 );
}
void makeSet( int x ){
p[x] = x;
rank[x] = 0;
elem[x] = 1;
}
bool isSet( int x, int y ) {
return !( p[x]<0 || p[y]<0 );
}
bool Union( int x, int y ){
if ( isSameSet(x,y) ) return false;
link( findSet(x), findSet(y) );
return true;
}
int findSet( int x ){
if ( x != p[x] ) p[x] = findSet( p[x] );
return p[x];
}
bool isSameSet( int x, int y ){
return ( findSet(x) == findSet(y) );
}
vector<int> rank, p, elem;
void link ( int x, int y ){
if ( rank[x] > rank[y] ){
p[y] = x;
elem[x] += elem[y];
} else {
p[x] = y;
elem[y] += elem[x];
if ( rank[x] == rank[y] ) rank[y]++;
}
}
};
inline bool bit(ll x, ll b)
{
return ((x>>b)&1)==1;
}
static unordered_map<ll,vector<ll>> memo;
vector<ll>& Next(int r, ll cur, bool first)
{
if ( memo.count(cur) ) return memo[cur];
ll w = cur&((1LL<<32)-1), g = cur>>32;
vector<ll> next;
for ( int i = 0; i < (1<<r); i++ ) {
ll a = w<<1, b = i<<1;
bool valid = true;
for ( int j = 0; j <= r; j++ ) {
ll a0 = a&3, b0 = b&3;
if ( a0==0&&b0==0 || a0==3&&b0==3 || a0==1&&b0==2 || a0==2&&b0==1 ) {
valid = false;
break;
}
a>>=1;
b>>=1;
}
if ( !valid ) {
continue;
}
DisjointSet d(2*r);
for ( int j = 0; j < r; j++ ) {
if ( bit(w,j) ) d.makeSet(j);
if ( bit(i,j) ) d.makeSet(j+r);
if ( bit(w,j) && bit(i,j) ) {
d.Union(j,j+r);
}
}
for ( int j = 0; j < r; j++ ) {
if ( !bit(w,j) ) continue;
for ( int k = j+1; k < r; k++ ) {
if ( !bit(w,k) ) continue;
if ( ((g>>(3*j))&7) == ((g>>(3*k))&7) ) {
d.Union(j,k);
}
}
}
for ( int j = 1; j < r; j++ ) {
if ( bit(i,j-1) && bit(i,j) ) {
if ( !d.Union(j+r-1, j+r) ) {
valid = false;
break;
}
}
}
if ( !valid ) {
continue;
}
bool checked[32] = {0};
for ( int j = 0; j < r; j++ ) {
if ( !bit(w,j) || checked[d.findSet(j)] ) continue;
bool connedted = false;
for ( int k = 0; k < r; k++ ) {
if ( !bit(i,k) ) continue;
if ( d.findSet(j) == d.findSet(k+r) ) {
checked[d.findSet(j)] = true;
connedted = true;
break;
}
}
if ( !connedted ) {
valid = false;
break;
}
}
if ( !valid ) {
continue;
}
ll gn[16] = {0};
int ig = 0;
map<ll,ll> mp;
for ( int j = 0; j < r; j++ ) {
if ( !bit(i,j) ) continue;
if ( mp.count(d.findSet(j+r)) ) {
gn[j] = mp[d.findSet(j+r)];
} else {
mp[d.findSet(j+r)] = ig;
gn[j] = ig;
ig++;
}
}
ll t = 0;
for ( int j = r-1; j >= 0; j-- ) {
t <<= 3;
t += gn[j];
}
next.push_back( (t<<32) + i );
}
return memo[cur] = next;
}
ll Count(int r, int c)
{
memo.clear();
if ( r > c ) swap(r,c);
map<ll,ll> dp;
dp[0] = 1;
for ( int i = 0; i < c; i++ ) {
map<ll,ll> dp2;
for ( auto p : dp ) {
auto& next = Next(r, p.first, i==0);
for ( auto nn : next ) {
dp2[nn] += p.second;
}
}
dp.swap(dp2);
}
ll sum = 0;
for ( auto it = dp.begin(); it != dp.end(); ++it ) {
ll w = it->first&((1LL<<32)-1);
w <<= 1;
bool valid = true;
for ( int j = 0; j <= r; j++ ) {
if ( (w&3) == 0 ) {
valid = false;
break;
}
w >>= 1;
}
if ( !valid ) {
continue;
}
ll g = it->first>>32;
if ( g ) {
continue;
}
sum += it->second;
}
return sum;
}
ll Solve(int r, int c, vector<vector<ll>>& ch, vector<vector<ll>>& cv)
{
memo.clear();
map<ll,ll> dp;
dp[0] = 0;
for ( int i = 0; i < c; i++ ) {
map<ll,ll> dp2;
for ( auto p : dp ) {
auto cur = p.first;
for ( auto next : Next(r, cur, i==0) ) {
ll cost = p.second;
for ( int j = 0; j < r; j++ ) {
if ( bit(cur,j) ^ bit(next,j) ) {
cost += cv[j][i];
}
}
ll t = next<<1;
for ( int j = 0; j <= r; j++ ) {
if ( bit(t,j) ^ bit(t,j+1) ) {
cost += ch[j][i];
}
}
if ( dp2.count(next)==0 || dp2[next] > cost ) {
dp2[next] = cost;
}
}
}
dp.swap(dp2);
}
ll ans = -1;
for ( auto it = dp.begin(); it != dp.end(); ++it ) {
ll w = it->first&((1LL<<32)-1);
w <<= 1;
bool valid = true;
for ( int j = 0; j <= r; j++ ) {
if ( (w&3) == 0 ) {
valid = false;
break;
}
w >>= 1;
}
if ( !valid ) {
continue;
}
ll g = it->first>>32;
if ( g ) {
continue;
}
ll cost = it->second;
for ( int j = 0; j < r; j++ ) {
if ( bit(it->first,j) ) {
cost += cv[j].back();
}
}
if ( ans < 0 || ans > cost ) {
ans = cost;
}
}
if ( ans < 0 ) return 0;
return ans;
}
int main()
{
int n = 0, m = 0;
cin >> m >> n;
vector<vector<ll>> ch, cv;
for ( int i = 0; i < m; i++ ) {
vector<ll> v(n-1,0);
for ( int j = 0; j < n-1; j++ ) {
cin >> v[j];
}
ch.push_back(v);
}
for ( int i = 0; i < m-1; i++ ) {
vector<ll> v(n,0);
for ( int j = 0; j < n; j++ ) {
cin >> v[j];
}
cv.push_back(v);
}
cout << Solve(m-1,n-1,ch,cv) << endl;
return 0;
}
Scor obtinut: 1.0
Submission ID: 464648679
Link challenge: https://www.hackerrank.com/challenges/tsp-grid/problem