I'm making a program for searching T-spin elevator. https://youtu.be/F3rhyJqusE4
But I have a problem with dealing spin_env variable, which is defined like this:
struct spin_environment {
vector< pair<int, int> > AND;
vector< vector <pair<int, int> > > OR;
};
spin_environment spin_env[4][2][5];
Especially spin_env[1][1][2].AND is corrupted during backtracking. When I initialized it, its size was 1. But during backtracking, suddenly the size of it bumped to 536870911, and all address of content in it can't have been found. But any other contents in spin_env, like spin_env[3][0][1].AND, didn't change.
So I thought this should be a memory problem, so I set reserved memory amount to 1GB at heap, 200MB at stack(default of this are both 1MB). But same problem has occurred and even when I took a memory snapshot, there was no change at how many memory I use.
I wonder why this error happened and how to fix it. Please help! The IDE I use is Visual Studio C++ 2017, building in x86 debug mode.
The whole code is described below (sorry for little comment)
#include<stdio.h>
#include<stdlib.h>
#include<utility>
#include<vector>
using namespace std;
vector<pair<int, int>> offset[4][2] = {
{ { { -1, 0 },{ -1, 1 } },{ { 1, 0 },{ 1, 1 } } },
{ { { 1, 0 },{ 0, 2 },{ 0, 2 },{ 1, 2 },{ 1,2 } },{ { 1, 0 },{ 0, 2 },{ 1, 2 } } },
{ { { 1, 0 } },{ { -1, 0 } } },
{ { { -1, 0 },{ 0, 2 },{ -1,2 } },{ { -1, 0 },{ 0, 2 },{ 0, 2 },{ -1,2 },{ -1,2 } } }
};
pair<int, int> block[4][4] = {
{ { 0, 0 },{ 1, 0 },{ -1, 0 },{ 0, 1 } },
{ { 0, 0 },{ 1, 0 },{ 0, -1 },{ 0, 1 } },
{ { 0, 0 },{ 1, 0 },{ -1, 0 },{ 0, -1 } },
{ { 0, 0 },{ 0, -1 },{ -1, 0 },{ 0, 1 } }
};
struct spin_environment {
vector< pair<int, int> > AND;
vector< vector <pair<int, int> > > OR;
};
spin_environment spin_env[4][2][5];
vector<int> state_order = { 0, 1, 2, 1, 0}, spin_order = { 0, 0, 0, 0 };
vector<vector<int>> answer;
int field[10][20];
pair<int, int> center = { 5, 18 };
void simulation(int);
pair<int, int> operator+ (pair<int, int> a, pair<int, int> b) {
return { a.first + b.first, a.second + b.second };
}
//initialize spin_env
void initialization() {
spin_env[0][0][0].AND = { { 0, -1 } };
spin_env[0][0][1].AND = { { 0, -1 },{ -1, -1 } };
spin_env[0][1][0].AND = { { 0, -1 } };
spin_env[0][1][1].AND = { { 0, -1 },{ 1, -1 } };
spin_env[1][0][0].AND = { { -1, 0 } };
spin_env[1][0][1].AND = { { -1, 0 },{ 1, -1 } };
spin_env[1][0][2].AND = { { -1, 0 },{ 2,0 } };
spin_env[1][0][2].OR = { { { 1, -1 },{ 2, -1 },{ 1, -2 } } };
spin_env[1][0][3].AND = { { -1, 0 },{ 1, -1 },{ -1, 2 } };
spin_env[1][0][4].AND = { { -1, 0 },{ 2,0 },{ -1, 2 } };
spin_env[1][0][4].OR = { { { 1, -1 },{ 2, -1 },{ 1, -2 } } };
spin_env[1][1][0].AND = { { -1, 0 } };
spin_env[1][1][1].AND = { { -1, 0 } };
spin_env[1][1][1].OR = { { { 1, -1 },{ 2, -1 } },{ { 2, 0 },{ 1, 1 } } };
spin_env[1][1][2].AND = { { -1, 0 } };
spin_env[1][1][2].OR = { { { 1, -1 },{ 2, -1 } },{ { 2, 0 },{ 1, 1 } },{ { -1, 2 },{ 0, 3 } } };
spin_env[2][0][0].AND = { { 0, 1 } };
spin_env[2][1][0].AND = { { 0, 1 } };
spin_env[3][0][0].AND = { { 1, 0 } };
spin_env[3][0][1].AND = { { 1, 0 } };
spin_env[3][0][1].OR = { { { -1, -1 },{ -2, -1 } },{ { -2, 0 },{ -1, 1 } } };
spin_env[3][0][2].AND = { { 1, 0 } };
spin_env[3][0][2].OR = { { { -1, -1 },{ -2, -1 } },{ { -2, 0 },{ -1, 1 } },{ { 1, 2 },{ 0, 3 } } };
spin_env[3][1][0].AND = { { 1, 0 } };
spin_env[3][1][1].AND = { { 1, 0 },{ -1, -1 } };
spin_env[3][1][2].AND = { { 1, 0 },{ -2,0 } };
spin_env[3][1][2].OR = { { { -1, -1 },{ -2, -1 },{ -1, -2 } } };
spin_env[3][1][3].AND = { { 1, 0 },{ -1, -1 },{ 1, 2 } };
spin_env[3][1][4].AND = { { 1, 0 },{ -2,0 },{ 1, 2 } };
spin_env[3][1][4].OR = { { { -1, -1 },{ -2, -1 },{ -1, -2 } } };
}
//subroutine function of simulation()
void subroutine(int index, int s, int c, int t, int sub_index) {
if (sub_index == spin_env[s][c][t].OR.size()) {
center.first += offset[s][c][t].first;
center.second -= offset[s][c][t].second;
simulation(index + 1);
center.first -= offset[s][c][t].first;
center.second += offset[s][c][t].second;
return;
}
int pass = 0;
for (int i = 0; i < spin_env[s][c][t].OR[sub_index].size(); i++) {
pair<int, int> temp = spin_env[s][c][t].OR[sub_index][i];
if (field[center.second - temp.second][center.first + temp.first] == 1)
{
pass = 1;
break;
}
}
if (pass) {
subroutine(index, s, c, t, sub_index + 1);
return;
}
for (int i = 0; i < spin_env[s][c][t].OR[sub_index].size(); i++) {
pair<int, int> temp = spin_env[s][c][t].OR[sub_index][i];
if (field[center.second - temp.second][center.first + temp.first] == -1)
continue;
field[center.second - temp.second][center.first + temp.first] = 1;
subroutine(index, s, c, t, sub_index + 1);
field[center.second - temp.second][center.first + temp.first] = 0;
}
}
//recursive function for backtracking
void simulation(int index) {
if (index == spin_order.size()) {
for (int y = 0; y < 10; y++) {
for (int x = 0; x < 20; x++) {
switch (field[y][x]) {
case 1:
printf("1 ");
break;
case -1:
printf("X ");
break;
default:
printf(" ");
break;
}
}
printf("\n");
}
return;
}
int s, c, t;
pair<int, int> temp;
s = state_order[index];
t = spin_order[index];
switch (state_order[index + 1] - s) {
case 1:
case -3:
c = 0;
break;
case -1:
case 3:
c = 1;
break;
}
for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
temp = spin_env[s][c][t].AND[j];
if (field[center.second - temp.second][center.first + temp.first] == -1)
{
return;
}
}
for (int j = 0; j < 4; j++) {
temp = block[state_order[index + 1]][j] + offset[s][c][t];
if (field[center.second - temp.second][center.first + temp.first] == 1)
{
return;
}
}
for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
temp = spin_env[s][c][t].AND[j];
field[center.second - temp.second][center.first + temp.first] = 1;
}
for (int j = 0; j < 4; j++) {
temp = block[state_order[index + 1]][j] + offset[s][c][t];
field[center.second - temp.second][center.first + temp.first] = -1;
}
subroutine(index, s, c, t, 0);
for (int j = 0; j < spin_env[s][c][t].AND.size(); j++) {
temp = spin_env[s][c][t].AND[j];
field[center.second - temp.second][center.first + temp.first] = 0;
}
for (int j = 0; j < 4; j++) {
temp = block[state_order[index + 1]][j] + offset[s][c][t];
field[center.second - temp.second][center.first + temp.first] = 0;
}
}
//recursive fuction for generate permutation
void permutation(int index) {
if (index == spin_order.size()) {
for (int j = 0; j < 4; j++) {
pair<int, int> temp = block[state_order[0]][j];
field[center.second - temp.second][center.first + temp.first] = -1;
}
simulation(0);
for (int j = 0; j < 4; j++) {
pair<int, int> temp = block[state_order[0]][j];
field[center.second - temp.second][center.first + temp.first] = 0;
}
return;
}
int k;
switch (state_order[index]) {
case 0:
k = 2;
break;
case 1:
if (state_order[index + 1] == 2) k = 5;
else k = 3;
break;
case 2:
k = 1;
break;
case 3:
if (state_order[index + 1] == 2) k = 5;
else k = 3;
break;
}
for (int i = 0; i < k; i++) {
spin_order[index] = i;
permutation(index + 1);
}
}
int main() {
initialization();
permutation(0);
}
Taking your code as-is, and simply changing the declaration of field to this detects you are going out of bounds in field:
std::vector<std::vector<int>> field(10, std::vector<int>(20));
Since you are using Visual Studio and you are running in debug mode, Visual C++ in debug mode detects out-of-bounds error conditions for std::vector. The error occurs in the permutation function:
if (index == spin_order.size()) {
for (int j = 0; j < 4; j++) {
pair<int, int> temp = block[state_order[0]][j];
field[center.second - temp.second][center.first + temp.first] = -1; // <-- Out of bounds here
When I run this program, the values of the std::pair<int, int> variables center and temp are as follows:
center = {5,18}
temp = {0,0}
The value of center.second - temp.second well exceeds the highest row index, which is 9, thus you are accessing the vector out-of-bounds. Anything after that line becomes a moot point since you are invoking undefined behavior.
Note that this was detected by changing the field declaration from using a raw array to std::vector. Since Visual Studio checks boundary conditions for std::vector and std::array in debug mode, you should take advantage of this and declare all of your arrays either as std::vector or std::array, so that you can detect these errors easily, or at least verify you are not going out-of bounds.
In addition, both vector and array have an at() member function you can use to detect boundary conditions, and sprinkling at() calls instead of using [ ] to access your elements is also another way to debug your application, or at least verify you have no boundary access issues.
Now how to fix this? You need to debug your code and see why center and/or temp is giving you values you didn't expect, or increase the size of your field vector/array to accommodate the index values.