首页 > 代码库 > WAP 2014 Examination 1

WAP 2014 Examination 1

2024-07-06 22:12:53   223人阅读

有两个考试，选了第1个。

题目的意思是W*H的方格，从S点到G点，中间要经过所有的n个checkpoint，求最短路。其中有的点不能走。

如果没有checkpoint的话，一个BFS就可以了。最开始想到贪心，从S开始，每次选择最近的那个点，但很容易找出反例来。

后来想，题目无非就是在S和G中安排n个点，以一定的次序使得依次连起来之后路径长度最短，因此一次添加一个点，假设之前已经安排好k个点，新加的点一共有k+1个位置可选。从这些可选点中选择最优解。但又找到了反例。

于是想到了动态规划，dp[i][j]表示已经选好了前i-1个点，选择j作为下一个添加的点的最优解。

令S为0，1到n位CP点，n+1为G点，于是dp[i][j]=min(dp[i-1][k]+dis[k][j],k从0到n)。需要注意的是要保证前i-1个点中没有j。最多18个CP，可以用一个整形（32位）来保存已经选择的点。还有一个需要注意的是k是从0到n，而不是到n+1，因为前i-1个点中不能有G点。

开始时对每个点BFS求任意两个点之间的最短路。

  1 #include<stdlib.h>
  2 #include<iostream>
  3 #include<stdio.h>
  4 #include<string.h>
  5 #include<vector>
  6 #include<list>
  7 #include<queue>
  8 #include<sstream>
  9 #include<map>
 10 #define inf 0x7fffffff
 11 #define LL long long
 12 #define MAX_E 1000000
 13 #define MAX_V 500
 14 #define MAX_N 105
 15 using namespace std;
 16 char mat[MAX_N][MAX_N];
 17 int bit[MAX_N][MAX_N];
 18 //对应坐标是否有CP
 19 int pos[MAX_N][MAX_N];
 20 int dis[MAX_N][MAX_N];
 21 int dp[MAX_N][MAX_N];
 22 int n=0;
 23 int W,H;
 24 struct Pos{
 25     int h,w;
 26     int levle;
 27     Pos(){
 28         h=w=levle=0;
 29     }
 30     Pos(int _h,int _w,int _levle){
 31         h=_h;
 32         w=_w;
 33         levle=_levle;
 34     }
 35 };
 36 int dh[4]={-1,0,1,0};
 37 int dw[4]={0,1,0,-1};
 38 void bfs(int h,int w){
 39     int s=pos[h][w];
 40     dis[s][s]=0;
 41     Pos start(h,w,0);
 42     queue<Pos> q;
 43     q.push(start);
 44     bool visited[MAX_N][MAX_N];
 45     memset(visited,0,sizeof(visited));
 46     visited[h][w]=1;
 47     while(!q.empty()){
 48         Pos t=q.front();
 49         q.pop();
 50         for(int i=0;i<4;i++){
 51             int hh=t.h+dh[i],ww=t.w+dw[i];
 52             //非墙壁
 53             if(hh>=0&&hh<H&&ww>=0&&ww<W&&mat[hh][ww]!=‘#‘&&!visited[hh][ww]){
 54                 Pos add(hh,ww,t.levle+1);
 55                 q.push(add);
 56                 visited[hh][ww]=1;
 57                 int p=pos[hh][ww];
 58                 if(p>=0&&dis[s][p]==inf){
 59                     dis[s][p]=add.levle;
 60                 }
 61             }
 62         }
 63     }
 64 }
 65 void solve(){
 66     //初始化起点，终点和CP点的位置
 67     //0为起点，1..n为CP点，n+1为终点
 68     n=0;
 69     memset(pos,-1,sizeof(pos));
 70     for(int i=0;i<H;i++){
 71         for(int j=0;j<W;j++){
 72             if(mat[i][j]==‘@‘){
 73                 pos[i][j]=++n;
 74             }
 75         }
 76     }
 77     for(int i=0;i<H;i++){
 78         for(int j=0;j<W;j++){
 79             if(mat[i][j]==‘S‘){
 80                 pos[i][j]=0;
 81             }
 82             if(mat[i][j]==‘G‘){
 83                 pos[i][j]=n+1;
 84             }
 85         }
 86     }
 87     //
 88     for(int i=0;i<=n+1;i++)
 89     {
 90         fill(dis[i],dis[i]+n+2,inf);
 91     }
 92     for(int i=0;i<H;i++)
 93         for(int j=0;j<W;j++){
 94             if(pos[i][j]>=0)
 95                 bfs(i,j);
 96         }
 97     for(int i=0;i<=n+1;i++)
 98         fill(dp[i],dp[i]+n+2,inf);
 99     memset(bit,0,sizeof(bit));
100     dp[0][0]=0;
101     bit[0][0]=1;
102     for(int i=1;i<=n+1;i++){
103         for(int j=1;j<=n+1;j++){
104             int M=inf,t=-1;
105             //注意，这里不能到n+1，第1到n步不能包含G
106             //若包含，在考虑最后一个点时，若前n个里均已包含G点，则此时求出的值为无穷大
107             for(int k=0;k<=n;k++){
108                 if(dp[i-1][k]!=inf&&(bit[i-1][k]&(1<<j))==0)
109                     if(M>dp[i-1][k]+dis[k][j]){
110                         M=dp[i-1][k]+dis[k][j];
111                         t=k;
112                     }
113             }
114             if (t!=-1) {
115                 dp[i][j]=M;
116                 bit[i][j]=bit[i-1][t]|(1<<j);
117             }
118         }
119     }
120     cout<<dp[n+1][n+1]<<endl;
121 }
122 class Orienteering{
123 public:
124     void main();
125 };
126 void Orienteering::main(){
127     while(scanf("%d%d",&W,&H)!=EOF){
128         getchar();
129         for(int i=0;i<H;i++)
130             scanf("%s",mat[i]);
131         solve();
132     }
133 }
134 int main(int argc, char* argv[]) {
135     Orienteering o;
136     o.main();
137     return 0;
138 }

提交之后才发现题目要求图不符合要求和不能到达终点时输出-1，%>_<%没处理


联系
我们