#include <iostream>
#include <vector>
#include <string>
using std::vector;
using std::string;
vector<bool> col;
vector<bool> diag;
vector<bool> antidiag;
    
void dfs(int i, int n, vector<vector<string> > &res, vector<string> &board) {
	if (i == n) {
		res.push_back(board);
		return;
	}
	
	for (int j = 0; j < n; j++) {
		if (!(col[j] && diag[i - j + n - 1] && antidiag[i + j])) {
			continue;        
		}
		
		board[i][j] = 'Q';  // Q stands for queen
		col[j] = diag[i - j + n - 1] = antidiag[i + j] = false;
		
		dfs(i + 1, n, res, board);
		
		board[i][j] = '.';
		col[j] = diag[i - j + n - 1] = antidiag[i + j] = true;
	}
}
vector<vector<string> > solveNQueens(int n) {
	vector<vector<string> > res;  
	
	col = vector<bool>(n, true);
	diag = vector<bool>(2 * n - 1, true);
	antidiag = vector<bool>(2 * n - 1, true);
	vector<string> board(n, string(n, '.'));  
	
	dfs(0, n, res, board);
	
	return res;
}
int main() {
	int n;	
	std::cout << "Pls input n: " << std::endl;
	std::cin >> n;
	vector<vector<string> > res = solveNQueens(n);
	for (int i = 0; i < res.size(); i++) {
		for (int j = 0; j < res[0].size(); j++) {
			std::cout << res[i][j] << std::endl;
		}
		std::cout << "==========" << std::endl;
	}
	return 0;
}

#include <iostream>
#include <list>
#include <unordered_map>
using std::list;
using std::unordered_map;
struct CacheItem {
  int key;
  int value;
  CacheItem(int k, int val) : key(k), value(val) { }
};
class LRUCache {
public:
    LRUCache(int capacity) : m_capacity(capacity) {
        
    }
    
    int get(int key) {
        if (m_map.find(key) != m_map.end()) {
            moveToHead(key);
            return m_map[key]->value;
        }
        return -1;
    }
    
    void set(int key, int value) {
        if (m_map.find(key) != m_map.end()) {
            m_map[key]->value = value;
            moveToHead(key);
        } else {
            if (m_cache.size() == m_capacity) {
                m_map.erase(m_cache.back().key);
                m_cache.pop_back();
            }
            CacheItem CacheItem(key, value);
            m_cache.push_front(CacheItem);
            m_map[key] = m_cache.begin();
        }
    }
    
private:
    void moveToHead(int key) {
        CacheItem updateCacheItem = *m_map[key];
        m_cache.erase(m_map[key]);
        m_cache.push_front(updateCacheItem);
        m_map[key] = m_cache.begin();
    }
    int m_capacity;
    list<CacheItem> m_cache;
    unordered_map<int, list<CacheItem>::iterator> m_map; 
};
int main() {
	LRUCache cache(2);
	cache.set(1, 11);
	cache.set(2, 22);
	std::cout << cache.get(1) << std::endl;       
	cache.set(3, 33);    
	std::cout << cache.get(2) << std::endl;       
	cache.set(4, 44);    
	std::cout << cache.get(1) << std::endl;       
	std::cout << cache.get(3) << std::endl;       
	std::cout << cache.get(4) << std::endl;       
	return 0;
}

int backPack(int m, vector<int> A) {
	vector<int> f(m + 1, 0);
	for (int i = 0; i < A.size(); i++) {
		for (int j = m; j >= 0; j--) {
			if (j >= A[i]) {
				f[j] = max(f[j], f[j - A[i]] + A[i]);
			}
		}
	}
	return f[m];
}

int backPack(int m, vector<int> A) {
	vector<bool> f(m + 1, false);
	f[0] = true;
	for (int i = 0; i < A.size(); i++) {
		for (int j = m; j >= 0; j--) {
			if (j >= A[i]) {
				f[j] = f[j] || f[j - A[i]];
			}
		}
	}
	for (int j = m; j >= 0; j--) {
		if (f[j]) {
			return j;
		}
	}
	return 0;
}

int backPackII(int m, vector<int> A, vector<int> V) {
	// f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i] ] + V[i])
	vector<int> f(m + 1, 0);
	for (int i = 0; i < A.size(); i++) {
		for (int j = m; j >= 0; j--) {
			if (j >= A[i] && (f[j] < f[j - A[i]] + V[i])) {
				f[j] = f[j - A[i]] + V[i];
			}
		}
	}
	return f[m];
}