Vladislav_133 26 мар 2010, 11:11
Программа, решающая задачу Игра в числа
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <math.h>
//A -- ходит по строкам
//B -- ходит по столбцам
//вариант - 5 ходов максимум
const int max=40;
int n; //размерность
int nx, ny; //начальный ход
int *num;
void rec(int, int, int);
int suma,sumb;
int mx[10000];
int my[10000];
int sh;
unsigned int no;
unsigned int asu;
int fg,er;
int vy();
int main()
{
int i,j;
//читаем размерность
fscanf(stdin,"%d",&n);
if(n>max)
{
fprintf(stdout,"Error 1!\n");
return 1;
}
//начальный ход nx ny
fscanf(stdin,"%d%d",&nx,&ny);
if(nx<1||ny<1||nx>n||ny>n)
{
fprintf(stdout,"Error 2!\n");
return 2;
}
//выделяем память для массива чисел
num = (int*)malloc(sizeof(int)*n*n);
asu=0;
//читаем квадрат
for(i=1; i<=n*n; i++)
{
er=fscanf(stdin,"%d",&num[i-1]);
if(er<=0)break;
// fprintf(stderr,"%d",num[i-1]);
asu=asu+num[i-1];
}
if(i<=n*n)
{
fprintf(stdout,"Error 3!\n");
return 3;
}
//приступаем к анализу
suma=0;sumb=0;sh=0;no=0;fg=0;
rec(nx,ny,0);
fprintf(stdout,"Total %d\n",no);
//конец
free(num);
return 0;
}
void rec(int x, int y, int pr)
{
int zn,k1,k2,u;
if(fg==1)return;
u=0;sh++;
if(sh>5)
{
sh--;
return;
}
zn=*(num + (x-1)*n + y-1);
*(num + (x-1)*n + y-1) = -1;
mx[sh-1]=x; my[sh-1]=y;
if(!pr)
{
//ход сделал A (по строкам)
suma=suma+zn;
asu=asu-zn;
// if(suma+suma<=asu)
{
for(k1=1; k1<=n; k1++)
{
if(*(num + (k1-1)*n + y-1)>=0)
{
u=1;
rec(k1,y,1);
}
}
}
}
else
{
//ход сделал B (по столбцам)
sumb=sumb+zn;
asu=asu-zn;
for(k2=1; k2<=n; k2++)
{
if(*(num + (x-1)*n + k2-1)>=0)
{
u=1;
rec(x,k2,0);
}
}
}
*(num + (x-1)*n + y-1) = zn;
asu=asu+zn;
if(!u||sh==5) vy();
sh--;
if(!pr)suma=suma-zn;else sumb=sumb-zn;
}
//
int vy()
{
int h;
if(sumb>=suma)
{
// for(h=0; h<sh; h++)
// {
// fprintf(stdout,"(%d,%d)",mx[h],my[h]);
// }
// fprintf(stdout,"a-%d b-%d \n",suma,sumb);
no++; //fg=1;
return 1;
}
return 0;
}