knightc1.cpp

骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题骑士控制问题

#include <fstream>
#include <string>
#include <math.h>
#include <time.h>
using   namespace   std;

int m = 0, n = 0, k = 0, level = 0; 
int minvalue = 0;
int tempminvalue = 0;
int arraylength = 0;
int tempi = 0, tempj = 0;
bool **p;
string pstr = "";
ifstream input("input.txt");
ofstream output("output.txt");

void init(bool isTrue){
	int i, j;
	if(p == NULL){
	    p = new bool* [m];
	    for(i = 0; i < m; i++){
		    p[i] = new bool [n];
		}
		minvalue = m * n;
		tempminvalue = m * n;
		arraylength = m*n;
	}

	for(i = 0; i < m; i++){
		for(j = 0; j < n; j++){
			p[i][j] = isTrue;
		}
	}
	level = 0;
}

void setTrue(int index){
	int temp = 0;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j]){
				continue;
			}
			else if(temp == index){
				p[i][j] = true;
				return;
			}
			else{
				temp++;
			}
		}
	}
}

void setFalse(int index, bool isTrue){
	if(!isTrue){
		int temp = 0;
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(!p[i][j]){
					continue;
				}
				else if(temp == index){
					p[i][j] = isTrue;
					tempi = i;
					tempj = j;
					return;
				}
				else{
					temp++;
				}
			}
		}
	}
	else{
		p[tempi][tempj] = isTrue;
	}
}


bool checkSingle(int i, int j){
	int count = 0;
	int x, y;

	x = i - 2;
	y = j - 1;
	if ((x >= 0) && (y >= 0)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i - 1;
	y = j - 2;
	if ((x >= 0) && (y >= 0)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i + 1;
	y = j - 2;
	if ((x < m) && (y >= 0)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i + 2;
	y = j - 1;
	if ((x < m) && (y >= 0)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i + 2;
	y = j + 1;
	if ((x < m) && (y < n)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i + 1;
	y = j + 2;
	if ((x < m) && (y < n)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i - 1;
	y = j + 2;
	if ((x >= 0) && (y < n)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}
	
	x = i - 2;
	y = j + 1;
	if ((x >= 0) && (y < n)){
		if(p[x][y] == true)
			count ++;
		if(count >= k)
			return true;
	}

	return false;
}

bool check(){
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(checkSingle(i, j)){
				continue;
			}
			else{
				return false;
			}
		}
	}
	return true;
}

void backtrack(int index, int* indexarray){
	
	int i = (int)(indexarray[index]/n);
	int j = indexarray[index]%n;
	p[i][j] = false;
	
	if(check()){
		tempminvalue--;
		if(tempminvalue < minvalue)
			minvalue = tempminvalue;
    	int maxdesc = arraylength - index;
		if((index + 1 <= arraylength - 1)&&((tempminvalue - maxdesc) < minvalue)){
			backtrack(index + 1, indexarray);
		}
		tempminvalue++;
	}
	p[i][j] = true;
	
	
	int maxdesc = arraylength - index;
	if((index + 1 <= arraylength - 1)&&((tempminvalue - maxdesc) < minvalue)){
		backtrack(index + 1, indexarray);
	}
}

void backtrack(){
  arraylength = tempminvalue;
  int *indexarray = new int[arraylength];
  int a = 0;
  for(int i = 0; i < m; i ++){
	  for(int j = 0;j < n;j++){
		  if(p[i][j]){
			  indexarray[a] = i*n + j;
			  a++;
		  }
	  }
  }
  backtrack(0, indexarray);
  delete[] indexarray;
}

void randdelete(){
    srand((long)(time(NULL)));
	int length = (int)(m*n/3);
	int tempLength = tempminvalue;
	int randValue;
    int i, j;
	for(i = 0; i < length; i++ , tempLength--){
		bool success = false;
		for(j = 0; j < 1000; j ++){
			randValue = rand() % tempLength; 
			setFalse(randValue, false);
			if(check()){
				tempminvalue = tempminvalue - 1;
				success =true;
				break;
			}
			else{
				setFalse(randValue, true);
			}
		}
		if(!success)
			break;
	}
	if(minvalue > tempminvalue)
		minvalue = tempminvalue;
}

void calculate(){
	init(true);

	int length = m * n;
	int tempLength = m * n;

	tempminvalue = m*n;
	if(minvalue > tempminvalue)
	    minvalue = tempminvalue;
	if(m*n > 36){
	  randdelete();
	}
    backtrack();
}


int main(){
	input >> m >> n >> k;

    if(k >= 3){
		output << "No solution!";
	}
	else if(k == 0){
		output << "0";
	}
	else{
		init(true);
		if(!check())
			output << "No solution!";
		else{
			if(m*n > 36){
				for(int i = 0; i < 1000;i++){
					calculate();
				}
			}
			else
				calculate();			
			output << minvalue;
		}
	}

	delete[] p;
	input.close();
	output.close();
    return 0;
}