搜索基础之马走日

``````1
5 4 0 0``````

``32``

``````#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int fx[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int map[11][11];
int num;int sum;
int n,m;
int beginn,endd;
void Dfs(int x0,int y0,int setp)
{
if(setp==num)
sum++;
else
{
for(int i=0; i<8; i++)
{
int a,b;
a=x0+fx[i][0];
b=y0+fx[i][1];
if(a>=0&&b>=0&&a<n&&b<m&&!map[a][b])
{
map[a][b]=1;
Dfs(a,b,setp+1);
map[a][b]=0;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(map,0,sizeof(map));
scanf("%d%d%d%d",&n,&m,&beginn,&endd);
num=n*m;
sum=0;
map[beginn][endd]=1;
Dfs(beginn,endd,1);
printf("%d\n",sum);
}
return 0;
}
``````

``````#include<stdio.h>
#include<string.h>
void mazouri(int x,int y,int Q);
int a[11][11],n,m,sum=0,nm;
void mazouri(int x,int y,int Q)
{
if(Q==n*m)
{
sum++;
return;
}
else
{
if(x-1>=0&&x-1<n&&y+2>=0&&y+2<m&&a[x-1][y+2]==0)
{
a[x-1][y+2]=1;
mazouri(x-1,y+2,Q+1);
a[x-1][y+2]=0;
}
if(x+1>=0&&x+1<n&&y+2>=0&&y+2<m&&a[x+1][y+2]==0)
{
a[x+1][y+2]=1;
mazouri(x+1,y+2,Q+1);
a[x+1][y+2]=0;
}
if(x+2>=0&&x+2<n&&y+1>=0&&y+1<m&&a[x+2][y+1]==0)
{
a[x+2][y+1]=1;
mazouri(x+2,y+1,Q+1);
a[x+2][y+1]=0;
}
if(x+2>=0&&x+2<n&&y-1>=0&&y-1<m&&a[x+2][y-1]==0)
{
a[x+2][y-1]=1;
mazouri(x+2,y-1,Q+1);
a[x+2][y-1]=0;
}
if(x+1>=0&&x+1<n&&y-2>=0&&y-2<m&&a[x+1][y-2]==0)
{
a[x+1][y-2]=1;
mazouri(x+1,y-2,Q+1);
a[x+1][y-2]=0;
}
if(x-1>=0&&x-1<n&&y-2>=0&&y-2<m&&a[x-1][y-2]==0)
{
a[x-1][y-2]=1;
mazouri(x-1,y-2,Q+1);
a[x-1][y-2]=0;
}
if(x-2>=0&&x-2<n&&y-1>=0&&y-1<m&&a[x-2][y-1]==0)
{
a[x-2][y-1]=1;
mazouri(x-2,y-1,Q+1);
a[x-2][y-1]=0;
}
if(x-2>=0&&x-2<n&&y+1>=0&&y+1<m&&a[x-2][y+1]==0)
{
a[x-2][y+1]=1;
mazouri(x-2,y+1,Q+1);
a[x-2][y+1]=0;
}
}
}
int main()
{
int T,x,y;
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
scanf("%d %d %d %d",&n,&m,&x,&y);
sum=0;
a[x][y]=1;
mazouri(x,y,1);
printf("%d\n",sum);
}
return 0;
}``````