简答题 偏难
#7194

冠军之路 当训练师眼神对上的那一刻,就会开始对战。 lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中,'.'代表可以行走的地面,'#'代表无…

冠军之路

当训练师眼神对上的那一刻,就会开始对战。

lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中,'.'代表可以行走的地面,'#'代表无法行走的岩石。'I'代表山洞的入口,即lxz现在所在的位置。'O'表示冠军之路的出口。lxz可以向上下左右四个方向行走。矩形的四周都是山洞的岩石,无法行走。

冠军之路中有一些精英训练师,他们可能面向上、下、左、右四个方向,在地图上用'w','a','s','d'表示,其中'w'表示向上。's'表示向下。'a'表示向左。'd'表示向右(这些位置不可行走)。如果lxz出现在精英训练师正对方向的一条线上,且没有被岩石或其他精英训练师阻挡,那么lxz就会与这个精英训练师进行对战。每位训练师只会与lxz对战一次。

为了通过冠军之路,lxz必须击败所有精英训练师。lxz希望找到一条击败所有精英训练师并走到冠军之路出口的最短路径。

时间限制:1000

内存限制:65536

输入

第一行是两个整数,N, M表示地图的大小。 0 < N, M <= 100 接下来是N行,每行M个字符,代表冠军之路的地图。训练师的个数不超过8

输出

一个整数,表示击败所有精英训练师并走到冠军之路出口的最短路径的长度。如果无法击败所有精英训练师或者无法到达出口,输出-1。

样例输入

3 3
Id.
...
Oa#

样例输出

8
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;limits&gt; #include &lt;queue&gt; #include &lt;vector&gt; using namespace std; /* 3 3 Id. ... Oa# */ struct point {   int x, y;   point(int x, int y) : x(x), y(y) {}   point() : x(0), y(0) {}   bool operator==(const point &amp;p) const { return x == p.x &amp;&amp; y == p.y; }   bool operator&lt;(const point &amp;p) const {     if (x == p.x)       return y &lt; p.y;     return x &lt; p.x;   } }; struct item {   point pt;   char c;   item(point p, char c) {     pt.x = p.x;     pt.y = p.y;     this-&gt;c = c;   } }; int direct[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; int a[105][105]; char d[105][105]; int pass[105][105]; vector&lt;vector&lt;point&gt;&gt; pts; vector&lt;item&gt; base; point bp, ep; int n, m; int bfs(point from, point to) {   queue&lt;point&gt; q;   char path[105][105] = {0};   q.push(from);   int ans = 0;   while (q.size()) {     // TODO     int size = q.size();     for (int k = 0; k &lt; size; k++) {       point cur = q.front();       q.pop();       path[cur.x][cur.y] = 1;       if (cur == to) {         return ans;       }       for (int i = 0; i &lt; 4; i++) {         point dst;         dst.x = cur.x + direct[i][0];         dst.y = cur.y + direct[i][1];         if (dst.x &gt;= n || dst.x &lt; 0)           continue;         if (dst.y &gt; m || dst.y &lt; 0)           continue;         if (path[dst.x][dst.y] == 0 &amp;&amp;             (d[dst.x][dst.y] == '.' || d[dst.x][dst.y] == 'O' ||              d[dst.x][dst.y] == 'I')) {           q.push(dst);         }       }     }     ans++;   }   return 0; } vector&lt;point&gt; getpoints(char pos, point p) {   vector&lt;point&gt; res;   string ss = ".IO";   if (pos == 'w') {     for (int i = p.x - 1; i &gt;= 0; i--)       if (ss.find(d[i][p.y]) != string::npos)         res.push_back(point(i, p.y));       else         break;   }   if (pos == 's') {     for (int i = p.x + 1; i &lt; m; i++)       if (ss.find(d[i][p.y]) != string::npos)         res.push_back(point(i, p.y));       else         break;   }   if (pos == 'a') {     for (int i = p.y - 1; i &gt;= 0; i--)       if (ss.find(d[p.x][i]) != string::npos)         res.push_back(point(p.x, i));       else         break;   }   if (pos == 'd') {     for (int i = p.y + 1; i &lt; n; i++)       if (ss.find(d[p.x][i]) != string::npos)         res.push_back(point(p.x, i));       else         break;   }   return res; } /* void showpath(int i, int j) {     if (i == j) return;     if (pass[i][j] == 0) {         printf("%d -&gt; %d \n",i , j);         route.push_back(j);     } else {         showpath(i, pass[i][j]);         showpath(pass[i][j], j);     } } */ int getMinBfs(point pt, vector&lt;int&gt; &amp;idx, vector&lt;int&gt; &amp;p,               vector&lt;vector&lt;point&gt;&gt; pts) {   int minval = INT32_MAX;   for (uint32_t i = 0; i &lt; pts.size(); i++) {     for (uint32_t j = 0; j &lt; pts[i].size(); j++) {       int dis = bfs(pt, pts[i][j]);       if (minval &gt; dis) {         minval = dis;         idx.clear(), p.clear();         idx.push_back(i), p.push_back(j);       } else if (minval == dis) {         idx.push_back(i), p.push_back(j);       }     }   }   return minval; } vector&lt;point&gt; getMinPoints(point pt, vector&lt;vector&lt;point&gt;&gt; pts) {   vector&lt;point&gt; res;   int idx, p;   for (uint32_t i = 0; i &lt; pts.size(); i++) {     int minval = INT32_MAX;     for (uint32_t j = 0; j &lt; pts[i].size(); j++) {       int dis = bfs(pt, pts[i][j]);       if (minval &gt; dis) {         minval = dis;         idx = i, p = j;       }     }     res.push_back(pts[idx][p]);   }   return res; } // 贪心法+bfs搜索计算最小路径 int getMinPath(point bp, point ep, vector&lt;vector&lt;point&gt;&gt; points) {   int sum = 0, minSum = INT32_MAX;   vector&lt;int&gt; idx, p;   vector&lt;point&gt; ap;   vector&lt;vector&lt;point&gt;&gt; apt;   point pt;   ap = getMinPoints(bp, points); // 获取与bp点距离最近的所有点   for (int x = 0; x &lt; ap.size(); x++) {     pt = bp;     sum = bfs(pt, ap[x]);     apt = points;     apt.erase(apt.begin() + x);     pt = ap[x]; // 设置为当前点     if (apt.size() &gt; 0) {       sum += getMinBfs(pt, idx, p, apt);       while (1) {         if (idx.size() &gt; 1) { // 有多个并列最近点的情况           int tmin = INT32_MAX, ts, k;           for (int i = 0; i &lt; idx.size(); i++) {             vector&lt;vector&lt;point&gt;&gt; tp = apt;             tp.erase(tp.begin() + idx[i]);             ts = getMinPath(apt[idx[i]][p[i]], ep,                             tp); // 计算以并列点为起点的路径             if (tmin &gt; ts) {               tmin = ts;               k = i;             } // 记录最小路径           }           idx[0] = idx[k], p[0] = p[k]; // 更新最小路径         }         pt = apt[idx[0]][p[0]];         apt.erase(apt.begin() + idx[0]);         if (apt.size() == 0)           break;         sum += getMinBfs(pt, idx, p, apt);       }     }     sum += bfs(pt, ep); // 加上到出口点的距离     if (minSum &gt; sum)       minSum = sum;   }   return minSum; } int main() {   cin &gt;&gt; n &gt;&gt; m;   for (int i = 0; i &lt; n; i++)     for (int j = 0; j &lt; m; j++) {       cin &gt;&gt; d[i][j];       if (d[i][j] != '#' &amp;&amp; d[i][j] != '.') {         base.push_back(item(point(i, j), d[i][j]));       }       if (d[i][j] == 'I')         bp = point(i, j);       if (d[i][j] == 'O')         ep = point(i, j);     }   // 扩展点,增加同方向的   for (int i = 0; i &lt; base.size(); i++) {     vector&lt;point&gt; vp;     if (base[i].c != 'I' &amp;&amp; base[i].c != 'O') {       vp = getpoints(base[i].c, base[i].pt);       pts.push_back(vp);     }   }   int sum1 = getMinPath(bp, ep, pts);          // 正向计算   int sum2 = getMinPath(ep, bp, pts);          // 反向计算   cout &lt;&lt; (sum1 &gt; sum2 ? sum2 : sum1) &lt;&lt; endl; // 取最小值   return 0; }</pre>
这道题暂未补解析。