如圖，有一8*8的方格，要求從任一點出發，到達不同色的另一個隨機格。
要求：1.必須經過所有的64格；
2.每個方格只能經過一次。
uj5u.com熱心網友回復：
是否一次只能到達相鄰格？uj5u.com熱心網友回復：
把它想象成一盤蚊香吧，螺旋的轉圈，不存在的地方先用臨時資料補上uj5u.com熱心網友回復：
只能上下左右移動，不能斜向移動
uj5u.com熱心網友回復：
邊標記：X方向： X11...X99
Y方向： Y11...Y99
二維陣列 XY[1..9][1..9]
移動： X 或者 Y 方向加或者減1
如果無法通過 X 或者 Y 方向加減一到達下一個未標記點，且已經標記數少于64，則失敗
uj5u.com熱心網友回復：
這是奧賽題，20多年前，就曾輔導參賽。uj5u.com熱心網友回復：
#include <stdio.h>
#define N 100
#define n 6
int main()
{
int dx[8],dy[8];
dx[0]= 2 , dy[0]= -1 ;
dx[1]= 1 , dy[1]= -2 ;
dx[2]= -1 , dy[2]= -2 ;
dx[3]= -2 , dy[3]= -1 ;
dx[4]= -2 , dy[4]= 1 ;
dx[5]= -1 , dy[5]= 2 ;
dx[6]= 1 , dy[6]= 2 ;
dx[7]= 2 , dy[7]= 1 ;
printf("********************\n");
for(int e=0;e<n;e++)
for(int r=0;r<n;r++)
{
int flag[N][N]={0};
int x[N],y[N],log[N]={0};
int beginx=e,beginy=r;
flag[beginx][beginy]=1;
int stepx=beginx,stepy=beginy;
x[0]=beginx,y[0]=beginy;
int t=1;
int sum=1;
while(t>0)
{
while(1)
{
if(log[t]==8)
{
log[t]=0;
goto L1;
}
stepx=stepx+dx[log[t]];
stepy=stepy+dy[log[t]];
if(stepx>=n||stepy>=n||stepx<0||stepy<0)
{
stepx-=dx[log[t]];
stepy-=dy[log[t]];
log[t]++;
goto L0;
}
if(flag[stepx][stepy]==1)
{
stepx-=dx[log[t]];
stepy-=dy[log[t]];
log[t]++;
}
if(flag[stepx][stepy]==0)
{
flag[stepx][stepy]=1;
sum++;
x[t]=stepx;
y[t]=stepy;
break;
}
L0:;
}
if(sum==n*n) goto write;
t++;
goto L2;
L1:
//flag[x[t]][y[t]]=0;
t--;
flag[x[t]][y[t]]=0;
sum--;
stepx=stepx-dx[log[t]];
stepy=stepy-dy[log[t]];
log[t]++;
L2:;
}
goto out;
write:
printf("\nbeginx=%d,beginy=%d\n",e,r);
out:;
}
return 0;
}
uj5u.com熱心網友回復：
那就一步一步的窮舉吧。
uj5u.com熱心網友回復：
窮舉很慢，應該有某一種特殊策略可以很快找到某種可行解吧uj5u.com熱心網友回復：
使用深度優先搜索。uj5u.com熱心網友回復：
可以試一試先遍歷同色格。然后再考慮不同色的格子。uj5u.com熱心網友回復：
定義上，左，右，下四個方向的權值為【4，3，2，1】如果為空的則為0，不能選擇。按照權值遍歷一次就可以了。可以試試。uj5u.com熱心網友回復：
是說先考慮對于顏色相同的兩個格子A和B，以A為起點B為終點進行全遍歷嗎？呵呵這是不可能做到的。
因為整個棋盤中紅色和綠色的格子數量是相等的，而且每一步只能從紅色跳到綠色，或者從綠色跳到紅色，所以，如果一條路徑以紅色開頭紅色結尾的話，整個路徑中紅色格子就會比綠色格子多一個，這就說明要么棋盤中某一個綠色格子沒有走到，要么有某一個紅色格子走了不止一遍。同樣的，也不可能出現由綠色開頭綠色結尾的遍歷路徑。
uj5u.com熱心網友回復：
只要把最后的不同色格定在最后的同色格旁邊就可以了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/104513.html
標籤：語言基礎/算法/系統設計