I wrote this C++ program but I got the following error:
*** Error in `/home/max4/Data/Programming/youcandoit/bin/Debug/youcandoit': free(): invalid pointer: 0x0000000000de2030 ***
Aborted
I was trying to solve this problem.
If anyone could help point out what mistakes I've made or if there are any clarifications that I can make for you, please leave a comment below.
Thanks, Max.
The following is my code.
#include <bits/stdc++.h>
#define dist second
#define key first
using namespace std;
int driver();
vector<int> inttovec(int);
int vectoint(vector<int>);
int bfs(int);
int value;
vector<int> stacks[8];
int n;
int bfs(int state) {
bitset<823543+2> vis;
vis.reset();
queue<pair<int, int>> qu; ///first is key second is dist
qu.push(make_pair(state, 0));
while (!qu.empty()) {
auto cur = qu.front(); qu.pop();
if (cur.key == value) return cur.dist;
vis[cur.key] = true;
vector<int> vcur = inttovec(cur.key);
printf("currently at ");
for (int i=0; i<n; ++i) printf("%d ", vcur[i]);
printf("\n");
for (int i=0; i<n; ++i) {
stacks[i].clear();
}
for (int i=0; i<n; ++i) {
stacks[vcur[i]].push_back(i);
}
for (int pos=0; pos<n; ++pos) {
if (stacks[pos].empty()) continue;
for (int to=max(0, pos-1); to<=min(n-1, pos+1); ++to) {
if (to == pos || !stacks[to].empty() && stacks[to][0] < stacks[pos][0]) continue;
vcur[stacks[pos][0]] = to; ///change
int newstate = vectoint(vcur); ///int-ify change
if (!vis[newstate]) {
printf("\tmove coin %d from pos %d to pos %d\n", stacks[pos][0], pos, to);
printf("\tto ");
for(int i=0; i<n; ++i) printf("%d ", vcur[i]);
printf("\n");
}
vcur[stacks[pos][0]] = pos; ///undo change
if (!vis[newstate]) {
qu.push(make_pair(newstate, cur.dist+1));
vis[newstate] = true;
}
}
}
}
printf("reached end of control\n");
return -1;
}
int vectoint(vector<int> vec2) {
int ret = 0;
for (int i=0; i<n; ++i) { ///technically this uses little endian instead of big or smth, but hey! go screw urself.
ret += (int)pow(n, i)*vec2[i];
}
return ret;
}
vector<int> inttovec(int num) {
vector<int> ret;
for (int i=n-1; i>=0; --i) {
//printf("%d: %d/pow = %d\n", i, num, num/(int)pow(n, i));
ret.push_back(num/(int)pow(n, i));
num %= (int) pow(n, i); /// could this ever be 0? probably not.
}
reverse(ret.begin(), ret.end());
return ret;
}
int driver() {
vector<int> positions(n);
int tmp;
for (int i=0; i<n; ++i) {
scanf("%d", &tmp); --tmp;
positions[tmp] = i;
}
int state = vectoint(positions);
int ans = bfs(state);
return ans;
}
int main()
{
freopen("test.txt", "r", stdin);
scanf("%d", &n);
vector<int> should;
for (int i=0; i<n; ++i) {
should.push_back(i);
}
value = vectoint(should);
printf("value %d\n", value);
for (auto i:inttovec(5)) {
cout << i << " ";
}
cout << endl;
while (n != 0) {
int ans = driver();
if (ans == -1) printf("IMPOSSIBLE\n");
else printf("%d\n", ans);
scanf("%d", &n);
}
}
Aucun commentaire:
Enregistrer un commentaire