poj2907DFS

題意：在一個最大20*20的矩形中，有一個起點，和另外許多個點，求從這個點出發經過所有點，再回到起點最少經過多少步。因為隻能上下左右地走，是以用到搜尋。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct Node
{
    int x,y,flag;
}node[100];
int n,sx,sy;
int ans,ret;
void Dfs(int xx,int yy,int ret,int cnt)
{
    if(ret==n)
    {
        int temp;
        temp=fabs(sx-xx)+fabs(sy-yy);
        if(temp+cnt<ans)
            ans=temp+cnt;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!node[i].flag)
        {
            node[i].flag=1;
            int temp=fabs(xx-node[i].x)+fabs(yy-node[i].y);
            Dfs(node[i].x,node[i].y,ret+1,cnt+temp);
            node[i].flag=0;
        }
    }

}
int main()
{
    int ca,l,w,i;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d%d",&l,&w);
        scanf("%d%d",&sx,&sy);
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&node[i].x,&node[i].y);
            node[i].flag=0;
        }
        ret=0,ans=99999999;
        Dfs(sx,sy,ret,0);
        printf("The shortest path has length %d\n",ans);
    }
    return 0;
}