[UVA] 11160 - Going Together＠Morris' Blog｜PChome Online 個人新聞台

2014-02-17 22:59:10| 人氣2,307| 回應0 | 上一篇 | 下一篇

[UVA] 11160 - Going Together

推薦 0 收藏 0 轉貼0 訂閱站台

G	Next Generation Contest 3	Time Limit: 3 seconds
	Going Together

You are playing a computer game in which three robots (Aneed, Ben and Cindy) are trapped in a labyrinth. Initially all three are situated in three different locations in the maze. There are three outlets through which the robots have to exit. As expected, there are several obstacles in the maze and the robots can't go through them.

The maze can be modeled as a square grid with N X N cells. The robots are placed on three different cells into the maze. You can command them to move. A single command will be activated for the three robots simultaneously. A robot will move to a new position if it is an empty cell within the maze or it is one of the target cells, otherwise the command will be ignored for that robot. Your task is to command them such a way that all of them are on three exit cells (in any order).

A move consists of one of the following (Each move takes 1 unit of time):

Move North	The robots move one cell north.
Move East	The robots move one cell east.
Move South	The robots move one cell south.
Move West	The robots move one cell west.

Each cell consists of one of the following characters:

A � Initial position of Aneed

B � Initial position of Ben

C � Initial position of Cindy

. � An empty cell

# - An obstacle

X � A target cell

You can assume that for every maze each of the letters (A B C) will appear exactly once and the letter X will appear exactly 3 times.

Input

The first line of input is an integer, T(T<50), that indicates the number of test cases. Each case starts with an integer N(2<N<10).� Each of the next N lines contain N characters each that fills up the maze.

Output

For each case, output the case number followed by the minimum time required. If it is impossible to move them as described, print �trapped� instead of the time.

Sample Input

Output for Sample Input

.....#.

.......

.#B....

...A.#.

.CX....

.X.X.#.

.#.....

ABC

...

XXX

ABC

###

XXX

Case 1: 2

Case 2: 2

Case 3: trapped

Problem Setter: Sohel Hafiz
Figure Drawing & Alternate Solution: Jane Alam Jan

Note:

The first case corresponds to the above picture.

題目描述：

三個人同時接收到相同指令並且操作，但三個人不能重疊在一起。
如果遇到撞牆或者是超出邊界，則會忽略該指令。

問至少幾步才能將三個人恰好放置在逃離三個出口上。

題目解法：

將三個人的座標壓縮，做一次 BFS。

#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
struct Pos {
   unsigned char x:4;
   unsigned char y:4;
   bool operator<(const Pos &a) const {
       if(x != a.x)
           return x < a.x;
       return y < a.y;
   }
   bool operator!=(const Pos &a) const {
       return x != a.x || y != a.y;
   }
};
struct State {
   Pos robot[3];
   void adjust() {
       sort(robot, robot+3);
   }
   bool operator<(const State &a) const {
       for(int i = 0; i < 3; i++)
           if(robot[i] != a.robot[i])
               return robot[i] < a.robot[i];
       return false;
   }
};
int main() {
   int testcase, cases = 0;
   int n;
   int i, j, k;
   char g[20][20];
   scanf("%d", &testcase);
   while(testcase--) {
       scanf("%d", &n);
       for(i = 0; i < n; i++)
           scanf("%s", &g[i]);
       State init;
       map<State, int> record;
       int cnt = 0;
       for(i = 0; i < n; i++) {
           for(j = 0; j < n; j++) {
               if(g[i][j] >= 'A' && g[i][j] <= 'C') {
                   init.robot[cnt].x = i, init.robot[cnt].y = j;
                   cnt++;
               }
           }
       }
       init.adjust();
       record[init] = 0;
       queue<State> Q;
       Q.push(init);
       int dx[] = {0, 0, 1, -1};
       int dy[] = {1, -1, 0, 0};
       int ret = -1;
       while(!Q.empty() && ret == -1) {
           State state = Q.front(), next;
           Q.pop();
           int step = record[state];
           for(i = 0; i < 4; i++) {
               for(j = 0; j < 3; j++) {
                   next.robot[j] = state.robot[j];
                   int x = next.robot[j].x + dx[i], y = next.robot[j].y + dy[i];
                   if(x < 0 || y < 0 || x >= n || y >= n || g[x][y] == '#') {
                       // ignore
                   } else {
                       next.robot[j].x = x;
                       next.robot[j].y = y;
                   }
               }
               while(1) {
                   next.adjust();
                   int ok = 1;
                   for(j = 1; j < 3; j++) {
                       if(next.robot[j].x == next.robot[j-1].x &&
                           next.robot[j].y == next.robot[j-1].y) {
                           ok = 0;
                           next.robot[j].x -= dx[i];
                           next.robot[j].y -= dy[i];
                       }
                   }
                   if(ok)   break;
               }
               int exit = 0;
               for(j = 0; j < 3; j++) {
                   if(g[next.robot[j].x][next.robot[j].y] == 'X')
                       exit++;
               }
               if(exit == 3) {
                   ret = step + 1;
                   break;
               }
               if(record.find(next) == record.end()) {
                   record[next] = step + 1;
                   Q.push(next);
               }
               /*printf("%d, %d\n", dx[i], dy[i]);
               char gg[25][25] = {};
               for(j = 0; j < 3; j++) {
                   gg[next.robot[j].x][next.robot[j].y] = 'A';
               }
               for(j = 0; j < n; j++, puts(""))
                   for(k = 0; k < n; k++)
                       if(g[j][k] == '#')
                           printf("#");
                       else
                           printf("%c", gg[j][k] ? gg[j][k] : '.');
               puts("-");*/
           }
       }
       printf("Case %d: ", ++cases);
       if(ret < 0)
           puts("trapped");
       else
           printf("%d\n", ret);
   }
   return 0;
}
/*
3
7
.....#.
.......
.#B....
...A.#.
.CX....
.X.X.#.
.#.....
*/

我要檢舉

#11160#Going Together#bfs

台長： Morris

您可能對以下文章有興趣

[UVA][Math] 11909 - Soya Milk

[UVA][圓周角] 12395 - Regular Convex Polygon

d733. 11329 - Curious Fleas

[UVA] 846 - Steps

人氣(2,307) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][並查集] 11323 - Satisfying Constraints
此分類上一篇:[UVA] 11140 - Little Ali's Little Brother

回應(0)