答复
BFS
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int dir[][2] = {{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
int q[51*51][3];
int step[51][51];
void output(int k)
{
if (q[k][2] == -1) {printf("(1,1)"); return;}
output(q[k][2]);
printf("->(%d,%d)",q[k][0],q[k][1]);
}
int main()
{
int head, tail, m, n, tx, ty, d;
memset(step, -1, sizeof(step));
scanf("%d%d",&n,&m);
q[0][0] = q[0][1] = 1; q[0][2] = -1;
step[1][1] = 0; head = 0; tail = 1;
while (head < tail) {
if (q[head][0] == n && q[head][1] == m) break;
for (d = 0 ; d < 8 ; d++) {
tx = q[head][0] + dir[d][0];
ty = q[head][1] + dir[d][1];
if (tx >= 1 && tx <= 50 && ty >= 1 && ty <= 50 && step[tx][ty] == -1) {
step[tx][ty] = step[q[head][0]][q[head][1]] + 1;
q[tail][0] = tx;
q[tail][1] = ty;
q[tail++][2] = head;
}
}
++head;
}
if (step[m][n] == -1) printf("error!\n");
else {
printf("STEP:%d\n",step[m][n]);
output(head);
printf("\n");
}
system("pause");
return 0;
}