poj 2688 Cleaning Robot (tsp问题)

 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=25;
25int w,h;
26char maze[N][N];
27int dist[N][N];
28int cnt;//机器人与脏地的个数
29int tag[N][N];//标记
30bool vist[N][N];
31struct node
32{
33    int x,y;
34    int step;
35    bool ok ()
36    {
37	if (x<1||x>h||y<1||y>w||vist[x][y]||maze[x][y]=='x')
38	    return false;
39	return true;
40    }
41}pos[N*N];

 1node robot;
 2int dir[4][2]={0,-1,0,1,-1,0,1,0};
 3void bfs(node p,int po)
 4{
 5    vist[p.x][p.y]=1;
 6    queue<node>q;
 7    q.push(p);
 8    while(!q.empty())
 9    {
10        node cur=q.front();
11        q.pop();
12        if(maze[cur.x][cur.y]=='o' || maze[cur.x][cur.y]=='*')
13            dist[po][tag[cur.x][cur.y]]=cur.step;
14        node next;
15        next.step=cur.step+1;
16        for(int i=0;i<4;i++)
17        {
18            next.x=cur.x+dir[i][0];
19            next.y=cur.y+dir[i][1];
20            if(!next.ok())
21                continue;
22            q.push(next);
23            vist[next.x][next.y]=1;
24        }
25    }
26}

 1int ans=inf;
 2bool vis[N];
 3void dfs(int x,int step,int s)
 4{
 5    if(step==cnt)
 6    {
 7        if(s<ans)
 8            ans=s;
 9        return ;
10    }
11    if(s>ans)
12        return ;
13    for(int j=1;j<=cnt;j++)
14    {
15        if(vis[j])
16            continue;
17        vis[j]=1;
18        dfs(j,step+1,s+dist[x][j]);
19        vis[j]=0;
20    }
21}

 1int main()
 2{
 3    while(~scanf("%d%d",&w,&h))
 4    {
 5        if(w==0&&h==0)
 6            break;
 7       // getchar();
 8        cnt=0;
 9        memset(pos,0,sizeof(pos));
10        memset(tag,0,sizeof(tag));
11        for(int i=1;i<=h;i++)
12        {
13            scanf("%s",maze[i]+1);
14            for(int j=1;j<=w;j++)
15                if (maze[i][j]=='o')
16                {
17                     pos[++cnt].x=i;
18                    pos[cnt].y=j;
19                    robot.x=i;
20                    robot.y=j;
21                    tag[i][j]=cnt;
22                }
23                else if(maze[i][j]=='*')
24                {
25                     pos[++cnt].x=i;
26                    pos[cnt].y=j;
27                    tag[i][j]=cnt;
28                }
29        }
30        for(int i=1;i<=cnt;i++)
31            for(int j=1;j<=cnt;j++)
32                if(i !=j)
33                    dist[i][j]=inf;
34                else
35                    dist[i][j]=0;
36        for(int i=1;i<=cnt;i++)
37        {    
38            memset(vist,0,sizeof(vist));
39            pos[i].step=0;
40            bfs(pos[i],i);
41        }
42        bool flag=1;
43        for(int i=1;i<=cnt && flag;i++)
44            for(int j=1;j<=cnt && flag;j++)
45                if(dist[i][j]==inf)
46                     flag=0;

 1        if(flag==0)
 2        {
 3            puts("-1");
 4            continue;
 5        }
 6        memset(vis,0,sizeof(vis));
 7        vis[tag[robot.x][robot.y]]=1;
 8        ans=inf;
 9        dfs(tag[robot.x][robot.y],1,0);
10        printf("%d\n",ans);

1    }
2    return 0;
3}