书影 - Entries for the tag poj

POJ 2688 广搜+深搜 BFS + DFS

qinjiannet@sina.com (在线疯狂) — Thu, 22 May 2014 13:02:20 +0800

Time Limit: 1000MS Memory Limit: 65536K

Description

Here, we want to solve path planning for a mobile robot cleaning a rectangular room floor with furniture.

Consider the room floor paved with square tiles whose size fits the cleaning robot (1 * 1). There are 'clean tiles' and 'dirty tiles', and the robot can change a 'dirty tile' to a 'clean tile' by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.

Your task is to write a program which computes the minimum number of moves for the robot to change all 'dirty tiles' to 'clean tiles', if ever possible.

Input

The input consists of multiple maps, each representing the size and arrangement of the room. A map is given in the following format.

w h
c11 c12 c13 ... c1w
c21 c22 c23 ... c2w
...
ch1 ch2 ch3 ... chw

The integers w and h are the lengths of the two sides of the floor of the room in terms of widths of floor tiles. w and h are less than or equal to 20. The character cyx represents what is initially on the tile with coordinates (x, y) as follows.

'.' : a clean tile
'*' : a dirty tile
'x' : a piece of furniture (obstacle)
'o' : the robot (initial position)

In the map the number of 'dirty tiles' does not exceed 10. There is only one 'robot'.

The end of the input is indicated by a line containing two zeros.

Output

For each map, your program should output a line containing the minimum number of moves. If the map includes 'dirty tiles' which the robot cannot reach, your program should output -1.

C语言代码：


#include <stdio.h>
#include <memory.h>
#define MAXN 20
typedef struct Node
{
  int step;
  int x,y;
}Node;
Node stack[10000],u;

typedef struct Point
{
  int x,y;
}Point;

Point point[15];

int min,sum;
int dist[15][15];
char map[MAXN][MAXN];
char grid[MAXN][MAXN];
int dx[] = {-1,0,0,1};
int dy[] = {0,1,-1,0};
int m,n;
int BFS(Point start, Point end)
{
  int sx = start.x;
  int sy = start.y;
  int ex = end.x;
  int ey = end.y;
  int head,tail,i,j,k;
  int flag = 0;

  for (k = 0; k < n; k ++)
  {
    for (j = 0; j < m; j ++)
    {
      map[k][j] = grid[k][j];
    }
  }

  map[sx][sy] = 'x';
  stack[0].x = sx;
  stack[0].y = sy;
  stack[0].step = 0;
  head = 0;
  tail = 1;

  while (head < tail)
  {
    u = stack[head ++];
    if (u.x == ex && u.y == ey)
    {
      flag = 1;
      break;
    }
    for (i = 0; i < 4; i ++)
    {
      if (u.x + dx[i] < n && u.x + dx[i] >= 0 && u.y + dy[i] < m && u.y + dy[i] >= 0 && map[u.x + dx[i]][u.y + dy[i]] != 'x')
      {
        stack[tail].x = u.x + dx[i];
        stack[tail].y = u.y + dy[i];
        stack[tail].step = u.step + 1;
        map[u.x + dx[i]][u.y + dy[i]] = 'x';
        tail ++;
      }
    }
  }
  if (flag)
    return u.step;
  else
    return -1;
}

int visited[15];
void DFS(int num,int add,int cur)
{
  int i;
  if (num == sum - 1)
  {
    if (add < min || min < 0)
    {
      min = add;
    }
  }
  else
  {
    for (i = 1; i < sum; i ++)
    {
      if ((add < min || min < 0) && !visited[i])
      {
        visited[i] = 1;
        DFS(num + 1,add + dist[cur][i],i);
      }
    }
  }
  visited[cur] = 0;
}
int main()
{
  int i,j,k;
  int head,tail;
  int flag;
  while (scanf("%d%d",&m,&n),m,n)
  {
    getchar();
    sum = 1;
    for (i = 0; i < n; i ++)
    {
      for (j = 0; j < m; j ++)
      {
        scanf("%c",&grid[i][j]);
        if (grid[i][j] == 'o')
        {
          point[0].x = i;
          point[0].y = j;
        }
        if (grid[i][j] == '*')
        {
          point[sum].x = i;
          point[sum].y = j;
          sum ++;
        }
      }
      getchar();
    }
    flag = 1;
    memset(dist,-1,sizeof(dist));
    for (i = 0; i < sum; i ++)
    {
      for (j = i; j < sum; j ++)
      {
        dist[i][j] = dist[j][i] = BFS(point[i],point[j]);
        if (dist[i][j] == -1)
        {
          flag = 0;
          break;
        }
      }
    }
    if (flag)
    {
      min = -1;
      memset(visited,0,sizeof(visited));
      visited[0] = 1;
      DFS(0,0,0);
      printf("%d\n",min);
    }
    else
      puts("-1");
  }
  return 0;
}

POJ 2513 字典树并查集

qinjiannet@sina.com (在线疯狂) — Sat, 03 May 2014 12:38:36 +0800

Colored Sticks (POJ 2513)
Time Limit: 5000MS Memory Limit: 128000K

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan
Sample Output

Possible
Hint

Huge input,scanf is recommended.

解题思路：使用字典树（Trie）与并查集（Union-Find）数据结构


#include <stdio.h>
#include <string.h>
#define MAXN 610000
typedef struct Trie
{
    int child[30];
    int isStr;
    int num;
}Trie;

int root, pCur;
Trie arr[MAXN];

char c1[20],c2[20];

int pi[MAXN],rank[MAXN],cap[MAXN];

int Find(int i)
{
    while (pi[i] != 0)
    {
        i = pi[i];
    }
    return i;
}

void Merge(int i, int j)
{
    i = Find(i);
    j = Find(j);
    if (i != j)
    {
        if (rank[i] > rank[j])
        {
            pi[j] = i;
        }
        else
        {
            pi[i] = j;
            if (rank[i] == rank[j])
            {
                rank[j] ++;
            }
        }
    }
}
int main()
{
    int len,i,j;
    int ca,cb;
    int total = 0;
    int amt = 0;
    int jdg,flag;
    int one;
    root = amt ++;

    while (scanf("%s%s",c1,c2) != EOF)
    {
        pCur = root;
        len = strlen(c1);
        for (i = 0; i < len; i ++)
        {
            if (arr[pCur].child[c1[i] - 'a'] == 0)
            {
                arr[pCur].child[c1[i] - 'a'] = amt ++;
            }
            pCur = arr[pCur].child[c1[i] - 'a'];
            if (i == len - 1)
            {
                if (arr[pCur].isStr == 0)
                {
                    arr[pCur].isStr = 1;
                    arr[pCur].num = total ++;
                }
                ca = arr[pCur].num;
                cap[ca] ++;
            }
        }
        pCur = root;
        len = strlen(c2);
        for (i = 0; i < len; i ++)
        {
            if (arr[pCur].child[c2[i] - 'a'] == 0)
            {
                arr[pCur].child[c2[i] - 'a'] = amt ++;
            }
            pCur = arr[pCur].child[c2[i] - 'a'];
            if (i == len - 1)
            {
                if (arr[pCur].isStr == 0)
                {
                    arr[pCur].isStr = 1;
                    arr[pCur].num = total ++;
                }
                cb = arr[pCur].num;
                cap[cb] ++;
            }
        }

        Merge(ca,cb);
    }

    flag = 1;
    jdg = Find(0);
    for (i = 1; i < total; i ++)
    {
        if (Find(i) != jdg)
        {
            //printf("Crush %d %d\n",Find(i),jdg);
            flag = 0;
            break;
        }
    }
    one = 0;
    if (flag)
    {
        for (i = 0; i < total; i ++)
        {
            //printf("cap[%d] %d\n",i+1,cap[i]);
            if (cap[i] % 2)
                one ++;
            if (one > 2)
            {
                flag = 0;
                break;
            }
        }
    }
    if (one == 1)
        flag = 0;

    if (flag)
    {
        puts("Possible");
    }
    else
    {
        puts("Impossible");
    }
    return 0;
}

POJ 2833 The Average 优先队列

qinjiannet@sina.com (在线疯狂) — Sat, 03 May 2014 12:21:23 +0800

The Average (POJ 2833)
Time Limit: 6000MS Memory Limit: 10000K
Case Time Limit: 4000MS

Description

In a speech contest, when a contestant finishes his speech, the judges will then grade his performance. The staff remove the highest grade and the lowest grade and compute the average of the rest as the contestant’s final grade. This is an easy problem because usually there are only several judges.

Let’s consider a generalized form of the problem above. Given n positive integers, remove the greatest n1 ones and the least n2 ones, and compute the average of the rest.

Input

The input consists of several test cases. Each test case consists two lines. The first line contains three integers n1, n2 and n (1 ≤ n1, n2 ≤ 10, n1 + n2 < n ≤ 5,000,000) separate by a single space. The second line contains n positive integers ai (1 ≤ ai ≤ 108 for all i s.t. 1 ≤ i ≤ n) separated by a single space. The last test case is followed by three zeroes.

Output

For each test case, output the average rounded to six digits after decimal point in a separate line.

Sample Input

1 2 5
1 2 3 4 5
4 2 10
2121187 902 485 531 843 582 652 926 220 155
0 0 0
Sample Output

3.500000
562.500000
Hint

This problem has very large input data. scanf and printf are recommended for C++ I/O.

The memory limit might not allow you to store everything in the memory.

解题思路：使用最小优先队列qmin与最大优先队列qmax维护最小值与最大值

C++代码如下：


#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue <int,vector<int>, less<int> > qmax;
priority_queue <int,vector<int>, greater<int> > qmin;
int main()
{
    int num,i,minus;
    long long sum;
    int n,m,k;
    int minsize,maxsize;
    while (scanf("%d%d%d",&m,&n,&k),m || n || k)
    {
        minsize = maxsize = 0;
        sum = 0;
        for (i = 0; i < k; i ++)
        {
            scanf("%d",&num);
            sum += (long long)num;
            if (minsize < m)
            {
                qmin.push(num);
                minsize ++;
            }
            else
            {
                if (num > qmin.top())
                {
                    qmin.pop();
                    qmin.push(num);
                }
            }
            if (maxsize < n)
            {
                qmax.push(num);
                maxsize ++;
            }
            else
            {
                if (num < qmax.top())
                {
                    qmax.pop();
                    qmax.push(num);
                }
            }
        }
        minus = 0;
        while (!qmax.empty())
        {
            minus += qmax.top();
            qmax.pop();
        }
        while (!qmin.empty())
        {
            minus += qmin.top();
            qmin.pop();
        }
        printf("%f\n",(1.0 * sum - (long long)minus) / (1.0 * (k - m - n)));
    }
    return 0;
}

书影 - Entries for the tag poj

POJ 2688 广搜+深搜 BFS + DFS

Description

Input

Output

POJ 2513 字典树 并查集

POJ 2833 The Average 优先队列

POJ 2513 字典树并查集