poj 2688 Cleaning Robot (tsp问题)
＿＿＿＿＿＿
好蠢，竟然没看出来这道题的不同之处，以为就是个搜
然后样例什么的都过了．．．
结果显然wa…
然后才发现，这道题应该是tsp问题．
解法是先跑一遍bfs,
对于所有的脏点和起点，得到没两个点之间的距离．
然后跑一遍dfs，枚举出所有的组合，同时更新答案．
晚安．
1/*************************************************************************
2 > File Name: code/poj/rr2688.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月16日 星期日 03时39分34秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=25;
32int w,h;
33char maze[N][N];
34int dist[N][N];
35int cnt;//机器人与脏地的个数
36int tag[N][N];//标记
37bool vist[N][N];
38struct node
39{
40 int x,y;
41 int step;
42 bool ok ()
43 {
44 if (x<1||x>h||y<1||y>w||vist[x][y]||maze[x][y]=='x')
45 return false;
46 return true;
47 }
48}pos[N*N];
49
50node robot;
51int dir[4][2]={0,-1,0,1,-1,0,1,0};
52void bfs(node p,int po)
53{
54 vist[p.x][p.y]=1;
55 queue<node>q;
56 q.push(p);
57 while(!q.empty())
58 {
59 node cur=q.front();
60 q.pop();
61 if(maze[cur.x][cur.y]=='o' || maze[cur.x][cur.y]=='*')
62 dist[po][tag[cur.x][cur.y]]=cur.step;
63 node next;
64 next.step=cur.step+1;
65 for(int i=0;i<4;i++)
66 {
67 next.x=cur.x+dir[i][0];
68 next.y=cur.y+dir[i][1];
69 if(!next.ok())
70 continue;
71 q.push(next);
72 vist[next.x][next.y]=1;
73 }
74 }
75}
76
77int ans=inf;
78bool vis[N];
79void dfs(int x,int step,int s)
80{
81 if(step==cnt)
82 {
83 if(s<ans)
84 ans=s;
85 return ;
86 }
87 if(s>ans)
88 return ;
89 for(int j=1;j<=cnt;j++)
90 {
91 if(vis[j])
92 continue;
93 vis[j]=1;
94 dfs(j,step+1,s+dist[x][j]);
95 vis[j]=0;
96 }
97}
98
99int main()
100{
101 while(~scanf("%d%d",&w,&h))
102 {
103 if(w==0&&h==0)
104 break;
105 // getchar();
106 cnt=0;
107 memset(pos,0,sizeof(pos));
108 memset(tag,0,sizeof(tag));
109 for(int i=1;i<=h;i++)
110 {
111 scanf("%s",maze[i]+1);
112 for(int j=1;j<=w;j++)
113 if (maze[i][j]=='o')
114 {
115 pos[++cnt].x=i;
116 pos[cnt].y=j;
117 robot.x=i;
118 robot.y=j;
119 tag[i][j]=cnt;
120 }
121 else if(maze[i][j]=='*')
122 {
123 pos[++cnt].x=i;
124 pos[cnt].y=j;
125 tag[i][j]=cnt;
126 }
127 }
128 for(int i=1;i<=cnt;i++)
129 for(int j=1;j<=cnt;j++)
130 if(i !=j)
131 dist[i][j]=inf;
132 else
133 dist[i][j]=0;
134 for(int i=1;i<=cnt;i++)
135 {
136 memset(vist,0,sizeof(vist));
137 pos[i].step=0;
138 bfs(pos[i],i);
139 }
140 bool flag=1;
141 for(int i=1;i<=cnt && flag;i++)
142 for(int j=1;j<=cnt && flag;j++)
143 if(dist[i][j]==inf)
144 flag=0;
145
146 if(flag==0)
147 {
148 puts("-1");
149 continue;
150 }
151 memset(vis,0,sizeof(vis));
152 vis[tag[robot.x][robot.y]]=1;
153 ans=inf;
154 dfs(tag[robot.x][robot.y],1,0);
155 printf("%d\n",ans);
156
157 }
158 return 0;
159}