CareerCup

it is really hard

#include<iostream>
using namespace std;
bool flag[7][7],res[7][7];
int result[7][7],r=0,maxi=0,n,m,c,x,next=1,temp[7][7],z[4][2],in[7][7];
int visited[7][7],used[40];


int get_next()
{
while(used[next]==1)
next++;
used[next]=1;
return next;
}


void input()
{
char ch;
int i,j,k,p;
ch=getchar();
string s;
for(i=1;i<=n;i++)
{
p=1;
getline(cin,s);
for(j=0;j<s.length();j++)
{
if(s[j]=='?')
{
in[i][p++]=0;
j++;
}
else
{
k=0;
while(s[j]!=' ' && j<s.length() )
{
k=k*10+int(s[j])-48;
j++;
}
in[i][p++]=k;
}
}
}
}


inline bool isrange(int i,int j)
{
return (i<=n && j<=m && i>0 && j>0);
}


int mark_visited(int a,int b,int j,int k)
{
int i,p=0;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && visited[a+z[i][0]][b+z[i][1]]==j)
{
visited[a+z[i][0]][b+z[i][1]]=k;
p++;
}
}
return p;
}


bool compare()
{
int i,j,k=0;
if(result[0][0]==1)
{result[0][0]=0;
return 1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(temp[i][j]<result[i][j])
return 1;
if(result[i][j]<temp[i][j])
return 0;
}
}
return 1;
}


int count_ones(int a,int b)
{
int k=0,i,j;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && flag[a+z[i][0]][b+z[i][1]])
{
k++;
if(temp[a+z[i][0]][b+z[i][1]]==0)
x=i;
}
}
return k;
}


void save()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
res[i][j]=flag[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
result[i][j]=temp[i][j];
}


void fill()
{
int a=1,b=1,i,k,j;
for(i=0;i<=n;i++)
for(k=0;k<=m;k++)
{
temp[i][k]=in[i][k];
used[i*n+k]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(in[i][j]>0)
used[in[i][j]]=1;
}
next=1;
while(next<=n*m)
{
if(temp[a][b]==0)
temp[a][b]=get_next();
i=count_ones(a,b);
if(i==1 && a*b!=1)
break;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && i!=x && temp[a+z[i][0]][b+z[i][1]]==0)
temp[a+z[i][0]][b+z[i][1]]=get_next();
}
if(x==2)
{
for(i=1;i<=b;i++)
temp[a][i]=(temp[a][i]==0 && flag[a][i]==0)?get_next():temp[a][i];
}
if(x==3)
{
for(i=1;i<=m;i++)
temp[a][i]=(temp[a][i]==0 && flag[a][i]==0)?get_next():temp[a][i];
}
a=a+z[x][0];
b=b+z[x][1];
}
}


void display()
{
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<res[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<result[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}


void compute(int a,int b,int i)
{
int p,j,k=r;
j=count_ones(a,b);
if(in[a][b]>0)
{
j=(in[a][b]>=c)?j:2;
}
if(isrange(a,b) && !flag[a][b] && j<=1 && c<=m*n)
{
flag[a][b]=1;
r++;
c=c+mark_visited(a,b,0,k+1);
compute(a,b-1,i);
compute(a,b+1,i);
compute(a-1,b,i);
compute(a+1,b,i);
c=c-mark_visited(a,b,k+1,0);
if(r==maxi && i==1)
{
fill();
if(compare())
save();
}
if(r>maxi)
maxi=r;
r=k;
flag[a][b]=0;
}
}


int main()
{
int i,j;
cin>>n>>m;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
{
temp[i][j]=0;
flag[i][j]=0;
visited[i][j]=0;
}
z[0][1]=z[1][0]=z[2][0]=z[3][1]=0;
z[2][1]=z[3][0]=1;
z[0][0]=z[1][1]=-1;
result[0][0]=1;
visited[1][1]=1;
input();
c=(in[1][1]>0)?in[1][1]:1;
compute(1,1,0);
compute(1,1,1);
cout<<maxi<<endl;
display();
return 0;
}

#include<stdio.h>
#include<conio.h>


int numImpCells = 0;
int output[6][6] = { 0 };


int countImpCells( int a[][6], int n, int m )
{
	int result = 0;
	bool temp[6][6] = { false };
	for(int i = 0; i < n; i++ )
	{
		for( int j = 0; j < m; j++ )
		{
			if( ( i == 0 ) && ( j== 0 ) )
			{
				temp[i][j] = true;
			}

			bool imp = true;
			if( ( i > 0 ) && temp[i-1][j] )
			{
				if( a[i][j] <= a[i-1][j] )
					imp = false;

				if( ( i > 1 ) && ( a[i][j] <= a[i-2][j] ) )
					imp = false;

				if( ( j > 0 ) && ( a[i][j] <= a[i-1][j-1] ) )
					imp = false;

				if( ( j < (m-1) ) && ( a[i][j] <= a[i-1][j+1] ) )
					imp = false;

				temp[i][j] = (imp || temp[i][j]);
			}

			if( ( j < (m-1) ) && temp[i][j+1] )
			{
				if( a[i][j] <= a[i][j+1] )
					imp = false;

				if( ( j < (m-2) ) && ( a[i][j] <= a[i][j+2] ) )
					imp = false;

				if( ( i > 0 ) && ( j < (m-1) ) && ( a[i][j] <= a[i-1][j+1] ) )
					imp = false;
				temp[i][j] = (imp || temp[i][j]);
			}

			if( ( i < (n-1) ) && temp[i+1][j] )
			{
				if( a[i][j] <= a[i+1][j] )
					imp = false;

				if( ( i < ( n-1)) && ( j < ( m - 1) ) && ( a[i][j] <= a[i+1][j+1] ) )
					imp = false;

				if( ( i < (n-2) ) && ( a[i][j] <= a[i+2][j] ) )
					imp = false;

				if( ( j > 0 ) && ( i < (n-1) ) && ( a[i][j] <= a[i+1][j-1] ) )
					imp = false;
				temp[i][j] = (imp || temp[i][j]);
			}

			if( ( j > 0 ) && temp[i][j-1] )
			{
				if( a[i][j] <= a[i][j-1] )
					imp = false;

				if( ( j > 1 ) && ( a[i][j] <= a[i][j-2] ) )
					imp = false;

				if( ( i > 0 ) && ( a[i][j] <= a[i-1][j-1] ) )
					imp = false;

				if( ( j > 0 ) && ( i < (n-1) ) && ( a[i][j] <= a[i+1][j-1] ) )
					imp = false;
				temp[i][j] = (imp || temp[i][j]);
			}
		}
		
	}

	for(int i = 0; i < n; i++ )
	{
		for( int j = 0; j < m; j++ )
		{
			if( temp[i][j] )
				result ++;
		}
	}

	return result;
}

void processsolution(int a[][6], int n, int m, bool usedNumbers[])
{
	int count = countImpCells( a, n , m) ;
	if( count > numImpCells )
	{
		numImpCells = count;

		for(int i = 0; i < n; i++ )
		{
			for( int j = 0; j < m; j++ )
			{
				output[i][j] = a[i][j];
			}
		}
	}

}

void backtracking(int a[][6], int n, int m, bool usedNumbers[])
{
	bool finished = true;
	for( int i = 1; i <= n*m; i++ )
	{
		if( usedNumbers[i] == false )
			finished = false;
	}

	if( finished == true )
		processsolution( a, n, m, usedNumbers );

	for(int i = 0; i < n; i++ )
	{
		for( int j = 0; j < m; j++ )
		{
			if( a[i][j] == -1 )
			{
				for( int k = 1; k <= n*m; k++ )
				{
					if( usedNumbers[k] == false )
					{
						a[i][j] = k;
						usedNumbers[k] = true;

						backtracking( a, n, m, usedNumbers );

						usedNumbers[k] = false;
						a[i][j] = -1;
					}
				}

			}
		}
	}

}

int main(int argc, char* argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	int a[6][6];
	bool usedNumbers[37] = {false};

	for(int i = 0; i < n; i++ )
	{
		for( int j = 0; j < m; j++ )
		{
			int result = scanf("%d", &a[i][j]);
			if( result <= 0 )
			{
				char c;
				scanf("%c", &c);
				a[i][j] = -1;
			}
			else
			{
				usedNumbers[a[i][j]] = true;
			}
		}
	}

	backtracking(a, n, m, usedNumbers);

	printf("\nResult: %d\n", numImpCells);
	for(int i = 0; i < n; i++ )
	{
		for( int j = 0; j < m; j++ )
		{
			printf("%d ", output[i][j]);
		}
		printf("\n");
	}

	getch();
	return 0;
}