|
#include <stdio.h>
#define X 10
#define Y 10
int chess[10][10] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
int curx = 0;
int cury = 0;
void print_chess(void)
{
int i,j;
for(i=0; i < 10; i++) {
for(j=0; j < 10; j++) {
printf("%d ",chess[i][j]);
}
printf("\n");
}
}
int get_son(int x, int y)
{
int number = 0;
if( (x<X-1) && (chess[x+1][y] == 0) )
{
number++;
}
if( (x>0) && (chess[x-1][y] == 0) )
{
number++;
}
if( (y<Y-1) && (chess[x][y+1] == 0) )
{
number++;
}
if( (y>0) && (chess[x][y-1] == 0) )
{
number++;
}
return number;
}
int get_next(int x, int y)
{
int min = 100;
int have_node = -1;
int temp = 0;
//pos->上下左右 1,2,3,4
int pos = 0;
int len = 100;
if((x != X-2)&&(x != 1)) {
if(x >= X >> 1) {
//下
len = X - x;
pos = 2;
}else{
//上
pos = 1;
len = x;
}
}
if((y != Y-2)&&(y != 1))
{
if(y >= Y >> 1) {
//右
if((Y-y) < len)
{
pos = 4;
}
}else{
//左
if(y < pos)
{
pos = 3;
}
}
}
if( (x>0) && (chess[x-1][y] == 0) )
{
have_node++;
min = get_son(x-1, y);
curx = x-1;
cury = y;
}
if( (y>0) && (chess[x][y-1] == 0) )
{
have_node++;
temp = get_son(x, y-1);
//相等的时候，如果是左边优先策略的时候，往左走。
if((min > temp) || ((min == temp)&&(pos == 3)))
{
min = temp;
curx = x;
cury = y-1;
}
}
if( (y<Y-1) && (chess[x][y+1] == 0) )
{
have_node++;
temp = get_son(x, y+1);
if((min > temp)||((min == temp)&&(pos == 4)))
{
min = temp;
curx = x;
cury = y+1;
}
}
if( (x<X-1) && (chess[x+1][y] == 0) )
{
have_node++;
temp = get_son(x+1, y);
if((min > temp) || ((min == temp)&&(pos == 2)))
{
min = temp;
curx = x+1;
cury = y;
}
}
chess[curx][cury] = 2;
return have_node;
}
int main(void)
{
curx = 4;
cury = 6;
chess[curx][cury] = 2;
while(get_next(curx, cury) >= 0)
{
print_chess();
}
return 0;
}
|
