poj 2688 Cleaning Robot (tsp问题)
______
好蠢,竟然没看出来这道题的不同之处,以为就是个搜
然后样例什么的都过了...
结果显然wa...
然后才发现,这道题应该是tsp问题.
解法是先跑一遍bfs,
对于所有的脏点和起点,得到没两个点之间的距离.
然后跑一遍dfs,枚举出所有的组合,同时更新答案.
晚安.
/*************************************************************************
> File Name: code/poj/rr2688.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月16日 星期日 03时39分34秒
************************************************************************/
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}