Multiply Optimizer

mult-optimizer.cpp

#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int N = 1000;

int vis[N][N]; pair<int, int> prev[N][N];

int main() {
	int val; cout << "Enter val to optimize: "; cin >> val;
	for (int i = 0; i< N; ++i)
		for (int j = 0; j < N; ++j)
			vis[i][j] = 0xDEADBEE;
	queue<int> qx, qy, qz;
	qx.push(1);
	qy.push(1);
	qz.push(0);
	vis[1][1] = 0;
	prev[1][1] = make_pair(-1, -1);
	#define Push(X,Y) if ((X) >= 0 && (Y) >= 0 && (X) < N && (Y) < N && vis[X][Y] > z + 1) {\
		qx.push(X);\
		qy.push(Y);\
		qz.push(z+1);\
		vis[X][Y] = z+1;\
		prev[X][Y] = make_pair(x, y);\
	}
	while (!qx.empty()) {
		int x = qx.front(); qx.pop();
		int y = qy.front(); qy.pop();
		int z = qz.front(); qz.pop();
		if (x == val) {
			cout << "Min steps: " << z << endl;
			stack<int> sx, sy;
			while (x != -1) {
				sx.push(x);
				sy.push(y);
				pair<int, int> pr = prev[x][y];
				x = pr.first;
				y = pr.second;
			}
			while (!sx.empty()) {
				printf("%dx %dx\n", sx.top(), sy.top());
				sx.pop(); sy.pop();
			}
			break;
		}
		if (vis[x][y] > z) continue;
		Push(x+y, y);
		Push(x, x+y);
		Push(x, y-x);
		Push(x-y, y);
		for (int i = 0; i < 10; ++i) {
			Push((x<<i), y);
			Push(x, (y<<i));
		}
	}
}