WA3 xelp
please give me test case, where my prog files, I've tested it on my friend's AC code and did not find mistake
thanks.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#define VI vector<int>
using namespace std;
map< VI , int > mp[10][10];
int p[4][6] =
{
{2 , 4 , 1 , 3 , 0 , 5}, // forw
{4 , 2 , 0 , 3 , 1 , 5},//backw
{0 , 1 , 5 , 2 , 3 , 4}, // left
{0 , 1 , 3 , 4 , 5 , 2} // right
};
int t[4][2] =
{{0,1},{0,-1},{-1,0},{1 , 0}};
string s1 , s2;
int xst , yst , xfin , yfin , i , j , n , m , a[10] , st , fin , x , y , ans = 1000000000 , nom , xx , yy;
struct str
{
int x , y;
vector<int> v;
str(){
x = y = 0;
}
str(int _x , int _y , vector<int> _v)
{
x = _x;
y = _y;
v = _v;
}
};
bool operator < (str a , str b)
{
return a.x < b.x || a.x == b.x && a.y < b.y || a.x == b.x && a.y == b.y && a.v < b.v;
}
bool operator == (str a , str b)
{
return a.x == b.x && a.y == b.y && a.v == b.v;
}
set<pair<int , str> > stt;
map<str , str> par;
void findans(str n)
{
if (n.x == xst && n.y == yst && mp[n.x][n.y][n.v] == a[4]); else
findans(par[n]);
cout<<char(n.x + 'a' - 1)<<char(n.y + '0')<<" ";
}
int main()
{
cin>>s1>>s2;
xst = s1[0] - 'a' + 1;
yst = s1[1] - '0';
xfin = s2[0] - 'a' + 1;
yfin = s2[1] - '0';
for (i = 0; i < 6; i++)
cin>>a[i];
if (s1 == s2)
{
cout<<a[4]<<" "<<s1;
return 0;
}
vector<int> v(a , a + 6);
vector<int> sle = v;
sort(sle.begin() , sle.end());
do
{
for (i = 1; i <= 8; i++)
for (j = 1; j <= 8; j++)
{
mp[i][j][sle] = 110000000;
stt.insert(make_pair(110000000 , str(i,j,sle)));
}
} while (next_permutation(sle.begin() , sle.end()));
mp[xst][yst][v] = a[4];
stt.erase( stt.find(make_pair(110000000 , str(xst,yst,v))) );
stt.insert(make_pair(a[4] , str(xst,yst,v)));
str stans;
while (1)
{
str w = stt.begin()->second;
int dis = stt.begin()->first;
if (dis == 110000000) break;
x = w.x;
y = w.y;
VI b = w.v , c(6);
for (i = 0; i < 4; i++)
{
xx = x + t[i][0];
yy = y + t[i][1];
if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8); else continue;
for (j = 0; j < 6 ; j++)
{
c[p[i][j]] = b[j];
}
if (mp[xx][yy][c] > dis + c[4])
{
mp[xx][yy][c] = dis + c[4];
par[str(xx , yy , c)] = w;
stt.insert(make_pair(dis + c[4] , str(xx , yy , c)));
if (xx == xfin && yy == yfin && mp[xx][yy][c] < ans)
{
ans = dis + c[4];
stans = str(xx ,yy , c);
}
}
}
stt.erase(stt.find(make_pair(dis , w)));
}
cout<<ans<<" ";
findans(stans);
return 0;
}