北大2018acm暑期课三简单搜索

迷宫问题

描述

定义一个二维数组： 

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

 

输入

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径，格式如样例所示。

样例输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

 

拿的以前的代码交的，就是普通的宽搜吧。

#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
using namespace std;
typedef pair<int, int> P;
#define N 5
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

int maze[N][N];
P path[N][N];
int d[N][N];
queue<P> que;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs()
{
    memset(d, 0x3f, sizeof d);
    que.push(P(0, 0));
    d[0][0] = 0;

    while(!que.empty()){
        P h = que.front(); que.pop();

        if(h.fi == 4 && h.se == 4) return;

        rep(i, 0, 3){
            int x = h.fi + dx[i], y = h.se + dy[i];
            if(x < 0 || x >= N || y < 0 || y >= N) continue;
            if(maze[x][y] == 1) continue;
            if(d[x][y] <= d[h.fi][h.se] + 1) continue;

            d[x][y] = d[h.fi][h.se] + 1;
            path[x][y] = h;
            que.push(P(x, y));
        }
    }
}

int main()
{
    //freopen("data.txt", "r", stdin);
    rep(i, 0, 4) rep(j, 0, 4) scanf("%d", &maze[i][j]);

    bfs();
    P ans[N * N];
    int l = 0;
    ans[l++] = P(4, 4);
    int x = 4, y = 4;
    while(!(x == 0 && y == 0)){
        ans[l++] = path[x][y];
        x = ans[l - 1].fi; y = ans[l - 1].se;
    }
    for(int i = l - 1; i >= 0; i--)
        printf("(%d, %d)\n", ans[i].fi, ans[i].se);

    return 0;
}

 

Pots

描述

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
2. DROP(i)      empty the pot i to the drain;
3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

输入

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

输出

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

样例输入

3 5 4

样例输出

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

也是拿的以前的代码交的，记得是几种操作容易写错。

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <string>
#include <queue>
using namespace std;
typedef pair<int, int> P;
#define N 101
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

int a, b, c;
string op[6] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
struct opt{
   int d, pa, x, y, z;
   opt(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0):d(a),pa(b),x(c),y(d),z(e){}
}path[N * N];
bool vis[N][N];

int bfs()
{
    int l = 0;
    path[l] = opt(0, -1, 0, 0);
    vis[0][0] = true;

    queue<opt> que;
    que.push(opt(1, l - 1, a, 0, 0));
    que.push(opt(1, l - 1, 0, b, 1));

    while(!que.empty()){
        path[l] = que.front();que.pop();
        opt & q = path[l];

        if(q.x == c || q.y == c){
            return l;
        }

        if(q.x != a && !vis[a][q.y]){
            vis[a][q.y] = true; que.push(opt(q.d + 1, l, a, q.y, 0));
        }
        if(q.y != b && !vis[q.x][b]){
            vis[q.x][b] = true; que.push(opt(q.d + 1, l, q.x, b, 1));
        }
        if(q.x != 0 && !vis[0][q.y]){
            vis[0][q.y] = true; que.push(opt(q.d + 1, l, 0, q.y, 2));
        }
        if(q.y != 0 && !vis[q.x][0]){
            vis[q.x][0] = true; que.push(opt(q.d + 1, l, q.x, 0, 3));
        }
        int k = min(q.x, b - q.y);
        if(k > 0 && !vis[q.x - k][q.y + k]){
            vis[q.x - k][q.y + k] = true;
            que.push(opt(q.d + 1, l, q.x - k, q.y + k, 4));
        }
        k = min(a - q.x, q.y);
        if(k > 0 && !vis[q.x + k][q.y - k]){
            vis[q.x + k][q.y - k] = true;
            que.push(opt(q.d + 1, l, q.x + k, q.y - k, 5));
        }

        l++;
    }

    return -1;
}

int main()
{
    cin >> a >> b >> c;

    int t = bfs();

    if(t == -1) printf("impossible\n");
    else{
        cout << path[t].d << endl;
        int ans[N * N], l = 0;
        ans[l++] = path[t].z;
        while(path[t].pa != -1){
            t = path[t].pa;
            ans[l++] = path[t].z;
           // cout << path[t].x << ' ' << path[t].y << endl;
        }
        for(int i = l - 1; i >= 0; i--)
            cout << op[ans[i]] << endl;
    }

    return 0;
}

鸣人和佐助

描述

佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？

输入

输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。

输出

输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。

样例输入

样例输入1
4 4 1
#@##
**##
###+
****

样例输入2
4 4 2
#@##
**##
###+
****

虽然鸣人蠢乎乎的，但是他也不会蠢到跑到一个从A跑到B把蛇杀死然后又跑回A，所以vis数组记录到达这个点的最小查克拉值来剪枝。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 210
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

char maze[N][N];
int n, m, t;
int sx, sy, tx, ty;
struct node{
    int x, y, w, d;
    node(int x, int y, int w, int d):x(x), y(y), w(w), d(d){}
};
int vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs()
{
    queue<node> que;
    memset(vis, -1, sizeof vis);
    vis[sx][sy] = t;
    que.push(node(sx, sy, t, 0));
    int x, y;

    while(!que.empty()) {
        node h = que.front(); que.pop();
        if(h.x == tx && h.y == ty) return h.d;
        rep(i, 0, 3) {
            x = h.x + dx[i]; y = h.y + dy[i];
            if(x < 0 || x >= n) continue;
            if(y < 0 || y >= m) continue;
            if(h.w <= vis[x][y]) continue;
            if(maze[x][y] == '#') {
                if(h.w == 0) continue;
                que.push(node(x, y, h.w - 1, h.d + 1));
                vis[x][y] = h.w - 1;
            }
            else{
                que.push(node(x, y, h.w, h.d + 1));
                vis[x][y] = h.w;
            }
        }
    }

    return -1;
}

int main()
{
   // freopen("data.txt", "r", stdin);

    while(~ scanf("%d%d%d", &n, &m, &t)) {
        rep(i, 0, n - 1) scanf("%s", maze[i]);
        rep(i, 0, n - 1) rep(j, 0, m - 1) {
            if(maze[i][j] == '@') sx = i, sy = j;
            else if(maze[i][j] == '+') tx = i, ty = j;
        }
        cout << bfs() << endl;
    }

    return 0;
}

 

拯救行动

描述

公主被恶人抓走，被关押在牢房的某个地方。牢房用N*M (N, M <= 200)的矩阵来表示。矩阵中的每项可以代表道路（@）、墙壁（#）、和守卫（x）。 
英勇的骑士（r）决定孤身一人去拯救公主（a）。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫，骑士一旦遇到守卫，必须杀死守卫才能继续前进。 
现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要1个单位时间，杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。

给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。

输入

第一行为一个整数S，表示输入的数据的组数（多组输入）
随后有S组数据，每组数据按如下格式输入 
1、两个整数代表N和M, (N, M <= 200). 
2、随后N行，每行有M个字符。"@"代表道路，"a"代表公主，"r"代表骑士，"x"代表守卫, "#"代表墙壁。

输出

如果拯救行动成功，输出一个整数，表示行动的最短时间。
如果不可能成功，输出"Impossible"

样例输入

2
7 8
#@#####@
#@a#@@[e-mail]
#@@#[e-mail]@@
@@#@@#@#
#@@@##@@
@#@@@@@@
@@@@@@@@ 
13 40
@[e-mail]@##[e-mail]#[e-mail]#xxxx##@#[e-mail]@@#x#@#x#@@[e-mail]#@x
xx###[e-mail]#@@##[e-mail]@@#@[e-mail]@#[e-mail]@@#[e-mail]#[e-mail]@[e-mail]
#@x#@x#x#@@##@@x#@xx#[e-mail]@x##@@@#@[e-mail]@[e-mail]
@##[e-mail]@@x#xx#@@#xxxx#@@[e-mail]@#@[e-mail]@@[e-mail]#@#[e-mail]#
@#xxxxx##@@x##[e-mail]@@#[e-mail]####@@@x#x##@#@
#xxx#@#x##[e-mail]@#[e-mail]@@[e-mail]#@#[e-mail]#####
#[e-mail]#@[e-mail]@@@##@x#xx#[e-mail]#xx#@#####x#@x
xx##@#@x##x##x#@x#@a#[e-mail]##@#@##[e-mail]#@@[e-mail]
x#x#@[e-mail]#x#@##@[e-mail]#[e-mail]##x##xx#@#[e-mail]@
#[e-mail]@#@###x##[e-mail]#@@#@@[e-mail]@@[e-mail]@@@##@@[e-mail]@x
x#[e-mail]###@xxx#@#x#@@###@#@##@x#@[e-mail]#@@#@@
#@#[e-mail]#x#x###@[e-mail]@xxx####[e-mail]##@x####xx#@x
#x#@x#x######@@#[e-mail]#xxxx#[e-mail]@@#xx#x#####@

样例输出

13
7

和上一题一样，骑士不会在某个点专门绕路去杀怪，所以记录到达每个点的最小时间来剪枝。第二点是时间t和步数d是不同的，而宽搜是根据d来入队列的，所以不能遇到一个就return，而是应该等队列清空。

当然这么写有点暴力，还可以拆点，在入队列时操作一下。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 210
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

struct node {
  int x, y, t, d;
  node(){}
  node(int x, int y, int t, int d):x(x), y(y), t(t), d(d){}
};
char maze[N][N];
int sx, sy, tx, ty;
int ans, cnt, n, m;
queue<node> que;
int vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs()
{
    while(!que.empty()) que.pop();
    memset(vis, INF, sizeof vis);
    vis[sx][sy] = 0;
    que.push(node(sx, sy, 0, 0));
    node tmp;
    int x, y, t, d, ans = INF;

    while(!que.empty()) {
        tmp = que.front(); que.pop();
        if(tmp.x == tx && tmp.y == ty) ans = min(ans, tmp.t);
    //    cout << tmp.x << ' ' << tmp.y << ' ' << tmp.t << ' ' << tmp.d << endl;
        rep(i, 0, 3) {
            x = tmp.x + dx[i]; y = tmp.y + dy[i];
            if(x < 0 || x >= n) continue;
            if(y < 0 || y >= m) continue;
            if(maze[x][y] == '#') continue;
            t = tmp.t + (maze[x][y] == 'x'?2:1);
            if(vis[x][y] <= t) continue;
            vis[x][y] = t;
            que.push(node(x, y, t, tmp.d + 1));
        }
    }

    return ans;
}

int main()
{
   // freopen("data.txt", "r", stdin);
    int t;
    scanf("%d", &t);

    while(t--) {
        scanf("%d%d", &n, &m);
        cnt = 0;
        //cout << n << ' ' << m << endl;
        rep(i, 0, n - 1) scanf("%s", maze[i]);

        rep(i, 0, n - 1) rep(j, 0, m - 1) if(maze[i][j] == 'a') tx = i, ty = j;
        else if(maze[i][j] == 'r') sx = i, sy = j;
        else if(maze[i][j] == 'x') cnt++;
//cout << sx <<' ' << sy << endl;
        if((ans = bfs()) >= INF) printf("Impossible\n");
        else printf("%d\n", ans);
    }

    return 0;
}

 

Saving Tang Monk

描述

《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.

During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.

Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace. But to rescue Tang Monk, Sun Wukong might need to get some keys and kill some snakes in his way.

The palace can be described as a matrix of characters. Each character stands for a room. In the matrix, 'K' represents the original position of Sun Wukong, 'T' represents the location of Tang Monk and 'S' stands for a room with a snake in it. Please note that there are only one 'K' and one 'T', and at most five snakes in the palace. And, '.' means a clear room as well '#' means a deadly room which Sun Wukong couldn't get in.

There may be some keys of different kinds scattered in the rooms, but there is at most one key in one room. There are at most 9 kinds of keys. A room with a key in it is represented by a digit(from '1' to '9'). For example, '1' means a room with a first kind key, '2' means a room with a second kind key, '3' means a room with a third kind key... etc. To save Tang Monk, Sun Wukong must get ALL kinds of keys(in other words, at least one key for each kind).

For each step, Sun Wukong could move to the adjacent rooms(except deadly rooms) in 4 directions(north,west,south and east), and each step took him one minute. If he entered a room in which a living snake stayed, he must kill the snake. Killing a snake also took one minute. If Sun Wukong entered a room where there is a key of kind N, Sun would get that key if and only if he had already got keys of kind 1,kind 2 ... and kind N-1. In other words, Sun Wukong must get a key of kind N before he could get a key of kind N+1 (N>=1). If Sun Wukong got all keys he needed and entered the room in which Tang Monk was cuffed, the rescue mission is completed. If Sun Wukong didn't get enough keys, he still could pass through Tang Monk's room. Since Sun Wukong was a impatient monkey, he wanted to save Tang Monk as quickly as possible. Please figure out the minimum time Sun Wukong needed to rescue Tang Monk.

 

 

 

 

输入

There are several test cases.

For each case, the first line includes two integers N and M(0 < N <= 100, 0
Then the N*N matrix follows.

The input ends with N = 0 and M = 0.

输出

For each test case, print the minimum time (in minute) Sun Wokong needed to save Tang Monk. If it's impossible for Sun Wokong to complete the mission, print "impossible".

样例输入

3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0

样例输出

5
impossible
8

因为要拿数量不一定的钥匙，所以题目一下子复杂了很多。如果每种钥匙只有一把，那么还能把问题分解为一段段的最短路，但是很多把就会走来走去的，要状压了。

节点除了时间，还要记录钥匙和已经打死的蛇的状态信息。记录蛇能确定走到蛇的一格时决定这蛇死了没有，走到钥匙有三种情况——已经拿到这种钥匙，没拿但是能拿或者不能拿这种钥匙。我用的钥匙和时间一起剪枝的，蛇没用。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

struct node {
    int x, y, keys, t, s;
    node(){}
    node(int x, int y, int k, int t, int s):x(x), y(y), keys(k), t(t), s(s){}
};
char maze[N][N];
int n, m, ans, l;
int sx, sy, tx, ty;
queue<node> que;
int t[N][N], k[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
map<P, int> mp;

int bfs()
{
    while(!que.empty()) que.pop();
    memset(t, INF, sizeof t);
    memset(k, 0, sizeof k);
    ans = INF;
    node h;
    int x, y, key, tt, ss;

    que.push(node(sx, sy, 0, 0, 0));
    t[0][0] = k[0][0] = 0;
//cout << ((1<<m)-1) << endl;

    while(!que.empty()) {
        h = que.front(); que.pop();
        //if(h.x==tx&&h.y==ty&&h.keys == (1 << m) - 1)cout << h.x <<' ' << h.y << ' ' <<h.keys<<' '<<h.t<<' '<<ans<<endl;
        if(h.x == tx && h.y == ty && h.keys == (1 << m) - 1) {ans = min(ans, h.t); continue;}

        rep(i, 0, 3) {
            x = h.x + dx[i], y = h.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= n) continue;
            if(maze[x][y] == '#') continue;
           // cout << x <<' ' <<y <<' ' <<tt <<endl;
            if(maze[x][y] == 'S' && !(h.s & (1<<mp[P(x, y)]))) tt = h.t + 2, ss = h.s | (1<<mp[P(x, y)]); //cout<<x<<' ' <<y<<' ' <<h.s<<' ' <<mp[P(x, y)]<<endl;
            else  tt = h.t + 1, ss = h.s;
            //if(maze[x][y]=='S'&&(h.s & mp[P(x, y)]))cout << x <<' ' <<y<< endl;
            if('1' <= maze[x][y] && maze[x][y] <= '9') {
                int num = maze[x][y] - '0' - 1;
                if(h.keys & (1 << num)) {
                    if(t[x][y] <= tt && k[x][y] >= h.keys) continue;
                    que.push(node(x, y, h.keys, tt, ss));
                    t[x][y] = tt;
                    k[x][y] = h.keys;
                }
                else if(num == 0 || (h.keys & (1 << (num - 1)))) {
                    que.push(node(x, y, h.keys | (1 << num), tt, ss));
                    t[x][y] = max(tt, t[x][y]);
                    k[x][y] = h.keys | (1 << num);
                }
                else {
                    if(t[x][y] <= tt && k[x][y] >= h.keys) continue;
                    que.push(node(x, y, h.keys, tt, ss));
                    t[x][y] = tt;
                    k[x][y] = h.keys;
                }
            }
            else{
                if(t[x][y] <= tt && k[x][y] >= h.keys) continue;
                que.push(node(x, y, h.keys, tt, ss));
                t[x][y] = tt;
                k[x][y] = h.keys;
            }
            //cout << x << ' ' << y << endl;
        }
    }
    return ans;
}

int main()
{
   // freopen("data.txt", "r", stdin);

    while(~scanf("%d%d", &n, &m) && n + m) {
        rep(i, 0, n - 1) scanf("%s", maze[i]);
        l = 0;
        mp.clear();
        rep(i, 0, n - 1) rep(j, 0, n - 1) {
            if(maze[i][j] == 'T') tx = i, ty = j;
            if(maze[i][j] == 'K') sx = i, sy = j;
            if(maze[i][j] == 'S') mp[P(i, j)] = ++l;
        }
      //  cout <<sx <<' ' <<sy<<' ' <<tx <<' ' <<ty <<endl;
        if((ans = bfs()) >= INF) puts("impossible");
        else printf("%d\n", ans);
    }

    return 0;
}

 

What a Ridiculous Election

描述

In country Light Tower, a presidential election is going on. There are two candidates,  Mr. X1andMr. X2, and both of them are not like good persons. One is called a liar and the other is called a maniac. They tear(Chinese English word, means defame) each other on TV face to face, on newspaper, on internet.......on all kinds of media. The country is tore into two parts because the people who support X1are almost as many as the people who support X2.

After the election day, X1and X2 get almost the same number of votes. No one gets enough votes to win. According to the law ofthe country, the Great Judge must decide who will be the president. But the judge doesn't want to offend half population of the country, so he randomly chooses a 6 years old kid Tom and authorize him to pick the president. Sounds weird? But the democracy in Light Tower is just like that.

The poor or lucky little kid Tom doesn't understand what is happening to his country. But he has his way to do his job. Tom's ao shu(Chinese English word, means some kind of weird math for kids) teacher just left him a puzzle a few days ago, Tom decide that he who solve that puzzle in a better way will be president. The ao shu teacher's puzzle is like this:

Given a string which consists of five digits('0'-'9'), like"02943", you should change "12345" into it by as few as possible operations. There are 3 kinds of operations:

1. Swap two adjacent digits.

2. Increase a digit by one. If the result exceeds 9, change it into it modulo10.

3. Double a digit. If the result exceeds 9, change it into it modulo 10.

You can use operation 2 at most three times, and use operation 3 at most twice.

As a melon eater(Chinese English again, means bystander), which candidate do you support? Please help him solve the puzzle.

 

输入

There are no more than 100,000 test cases.
Each test case is a string which consists of 5 digits.

输出

For each case, print the minimum number of operations must be used to change "12345" into the given string. If there is no solution, print -1.

样例输入

12435
99999
12374

样例输出

1
-1
3

本来想不就是个简单版本的八数码，结果题目意思就理解错了wa了好几发Orz。

注意操作23的数量也要去重。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 110
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

struct node {
    char s[6];
    int op2, op3, d;
    node(){}
    node(char * a, int b, int c, int d) {
        strcpy(s, a); op2 = b; op3 = c;this->d = d;
    }
};
char s[6], ans[6], h[6];
queue<node> que;
int num;
node tmp;
int cnt[100000][4][3];

int get(char * t)
{
    int ret = 0;
    rep(i, 0, 4) ret = ret * 10 + t[i] - '0';
    return ret;
}

void bfs()
{
    while(!que.empty()) que.pop();
    que.push(node(ans, 3, 2, 1));
    cnt[get(ans)][3][2] = 1;

    while(!que.empty()) {
        tmp = que.front(); que.pop();
        memcpy(h, tmp.s, sizeof tmp.s);

        rep(i, 0, 3) {
            swap(h[i], h[i + 1]);
          //  if(strcmp(h, "12435") == 0) cout << tmp.d + 1 << endl;
            if(!cnt[get(h)][tmp.op2][tmp.op3]){
                que.push(node(h, tmp.op2, tmp.op3, tmp.d + 1));
                cnt[get(h)][tmp.op2][tmp.op3] = tmp.d + 1;
            }
            swap(h[i], h[i + 1]);
        }

        if(tmp.op2)
        rep(i, 0, 4) {
            num = h[i] - '0';
            h[i] = char((num + 1) % 10 + '0');
            if(!cnt[get(h)][tmp.op2 - 1][tmp.op3]){
                que.push(node(h, tmp.op2 - 1, tmp.op3, tmp.d + 1));
                cnt[get(h)][tmp.op2 - 1][tmp.op3] = tmp.d + 1;
            }
            h[i] = num + '0';
        }

        if(tmp.op3)
        rep(i, 0, 4) {
            num = h[i] - '0';
            h[i] = char((num << 1) % 10 + '0');
//            if(strcmp(tmp.s, "12344") == 0) cout << h << endl;
            if(!cnt[get(h)][tmp.op2][tmp.op3 - 1]){
                if(!strcmp(h, ans)) continue;
                que.push(node(h, tmp.op2, tmp.op3 - 1, tmp.d + 1));
                cnt[get(h)][tmp.op2][tmp.op3 - 1] = tmp.d + 1;
            }
            h[i] = num + '0';
        }
    }
}

int main()
{
   // freopen("data.txt", "r", stdin);

    rep(i, 0, 4) ans[i] = i + '0' + 1;
    ans[5] = '\0';
    bfs();

    while(~scanf("%s", s)){
        int tmp = get(s), t = INF;
        rep(i, 0, 3) rep(j, 0, 2)
            if(cnt[tmp][i][j] > 0 && cnt[tmp][i][j] < t)
                t = cnt[tmp][i][j];
        printf("%d\n", t == INF?-1:t - 1);
    }

    return 0;
}

红与黑

描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。

输出

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

样例输出

45

以前的代码。

#include <iostream>
using namespace std;

char maze[105][105];
int W, H;
int num;//计数器
//四个方向向量
int vx[] = {0, 0, 1, -1};
int vy[] = {-1,1, 0,  0};

void sou(int x, int y)
{
    //走过的不再计数
    maze[x][y] = '#';
    num++;

    //四个方向深搜
    for(int i = 0; i <= 3; i++)
    {
        int nx = x + vx[i], ny = y + vy[i];

        if(0 <= nx && nx < H && 0 <= ny && ny <= W && maze[nx][ny] == '.')
            sou(nx, ny);
    }
}

int main()
{
    while(cin >> W >> H && W)
    {
        num = 0;

        for(int i = 0; i < H; i++)
            cin >> maze[i];

        for(int i = 0; i < H; i++)
            for(int j = 0; j < W; j++)
        {
            if(maze[i][j] == '@')
            {
                sou(i, j);
                break;
            }
        }

        cout << num << endl;
    }

    return 0;
}

海贼王之伟大航路

描述

“我是要成为海贼王的男人！”，路飞一边喊着这样的口号，一边和他的伙伴们一起踏上了伟大航路的艰险历程。

路飞他们伟大航路行程的起点是罗格镇，终点是拉夫德鲁（那里藏匿着“唯一的大秘宝”——ONE PIECE）。而航程中间，则是各式各样的岛屿。

因为伟大航路上的气候十分异常，所以来往任意两个岛屿之间的时间差别很大，从A岛到B岛可能需要1天，而从B岛到A岛则可能需要1年。当然，任意两个岛之间的航行时间虽然差别很大，但都是已知的。

现在假设路飞一行从罗格镇（起点）出发，遍历伟大航路中间所有的岛屿（但是已经经过的岛屿不能再次经过），最后到达拉夫德鲁（终点）。假设他们在岛上不作任何的停留，请问，他们最少需要花费多少时间才能到达终点？

输入

输入数据包含多行。
第一行包含一个整数N(2 < N ≤ 16)，代表伟大航路上一共有N个岛屿（包含起点的罗格镇和终点的拉夫德鲁）。其中，起点的编号为1，终点的编号为N。
之后的N行每一行包含N个整数，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个岛屿出发到第j个岛屿需要的时间t(0 < t < 10000)。第i行第i个整数为0。

输出

输出为一个整数，代表路飞一行从起点遍历所有中间岛屿（不重复）之后到达终点所需要的最少的时间。

样例输入

样例输入1：
4
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0

样例输入2：
5
0 18 13 98 8
89 0 45 78 43 
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0

样例输出

样例输出1：
100

样例输出2：
137

提示

提示：
对于样例输入1：路飞选择从起点岛屿1出发，依次经过岛屿3，岛屿2，最后到达终点岛屿4。花费时间为20+50+30=100。
对于样例输入2：可能的路径及总时间为：
1,2,3,4,5: 18+45+96+52=211
1,2,4,3,5: 18+78+29+12=137
1,3,2,4,5: 13+38+78+52=181
1,3,4,2,5: 13+96+19+43=171
1,4,2,3,5: 98+19+45+12=174
1,4,3,2,5: 98+29+38+43=208
所以最短的时间花费为137
单纯的枚举在N=16时需要14!次运算，一定会超时。

 

在一个完全图里从起点到终点经过所有点的最短路。这题有两种写法——dp和搜索。

dp的话是状压dp。定义状态dp[s][e]为最后走到点s状态为e的最值。我一开始直接写的node  dp[e]，node里存e和上一个状态转移到这个状态e的最后一个点，然后两层循环枚举当前状态和当前状态的前一个状态。。。这么写就把上一个状态的最后一个岛固定死了，只能由上一个状态的的最后一个岛屿转移到当前状态，而真正的情况是上一个状态的很多岛都可能转移到当前状态。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 20
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define mid(l,r) (((l)+(r))>>1)
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

int n, t;
int g[N][N];
int dp[20][(1 << 16) + 20];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
    #endif

    while(~scanf("%d", &n)) {
        rep(i, 1, n) rep(j, 1, n) scanf("%d", &g[i][j]);
        int m = (1 << n) - 1;
        memset(dp, INF, sizeof dp);
        dp[1][1] = 0;
        rep(i, 1, m) rep(j, 1, n) if(i & (1 << (j - 1))){
            rep(k, 1, n) if(j != k && i & (1 << (k - 1)))
                dp[j][i] = min(dp[j][i], dp[k][i ^ (1 << (j - 1))] + g[k][j]);
        }

        printf("%d\n", dp[n][m]);
    }

    return 0;
}

搜索的剪枝也要状压。。。。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 20
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define mid(l,r) (((l)+(r))>>1)
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

int n, t, ans;
int g[N][N];
int st[N][1<<N];
bool vis[N];

void dfs(int x, int deep, int v, int s)
{
    if(v >= ans) return;
    if(deep == n) {
        ans = min(ans, v);
        return;
    }

    if(st[x][s] > v) st[x][s] = v;
    else return;

    rep(i, 2, n) {
        if(vis[i]) continue;
        if(i == n && deep < n - 1) break;
        vis[i] = true;
        dfs(i, deep + 1, v + g[x][i], s|(1<<(i-1)));
        vis[i] = false;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
    #endif

    while(~scanf("%d", &n)) {
        rep(i, 1, n) rep(j, 1, n) scanf("%d", &g[i][j]);
        ans = INF;
        memset(vis, false, sizeof vis);
        memset(st, INF, sizeof st);
        dfs(1, 1, 0, 1);
        printf("%d\n", ans);
    }

    return 0;
}

 

泰国佛塔

描述

泰囧，大家应该都看过。不知道大家有没有注意到宝宝虔诚祈福的寺庙里的金灿灿的佛塔。      

众所周知，泰国佛塔外面是贴金的，而且金箔过一段时间需要修补。泰国经济自上世纪末就不景气，贴金的开支对于寺庙来说也是个比较大的负担。          

这里请同学来帮助寺庙设计下佛塔的模型，以使佛塔的外表面（最下层的下底面除外）的面积最小。从而节省金箔开支。      

这里抽象佛塔形状为，一层层的圆柱体，自底向上直径递减。制作一个体积为Nπ的M层佛塔。设从下往上数第i(1 <= i <= M)层佛塔是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri> Ri+1且Hi> Hi+1。令外表面面积为Q=Sπ。      

请编程，对于给出的N和M，找出佛塔的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）

输入

包括若干行。每行包括两个整数N（N <= 10000）、M(M <= 20)，代表一组测试数据。分别表示待建造的佛塔的体积为Nπ,和佛塔的层数为M。

输出

对于每组测试数据，输出占一行：一个正整数S（若无解则S = 0）。

样例输入

100 2
27 15

样例输出

68
0

老师讲过，就是各种剪枝一起怼。

#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 20
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define mid(l,r) (((l)+(r))>>1)
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)

int n, m;
int minArea;
int area, maxr, maxh;
int minv[25], mina[25];

int maxV(int d, int r, int h)
{
    int v = 0;
    rep(i, 1, d) {
        v += r * r * h;
        r--; h--;
    }
    return v;
}

void dfs(int v, int d, int r, int h)
{
    if(d == 0) {
        if(v) return;
        minArea = min(minArea, area);
        return;
    }

    if(minv[d] > v) return;
    if(area + mina[d] >= minArea) return;
    if(r < d || h < d) return;
    if(v > maxV(d, r, h)) return;

    for(int i = r; i >= d; i--) {
        if(d == m) area     = i * i;
        for(int j = h; j >= d; j--){
            area += 2 * i * j;
            if(v >= i * i * j)
                dfs(v - i * i * j, d - 1, i - 1, j - 1);
            area -= 2 * i * j;
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("data.txt", "r", stdin);
    #endif

    while(~scanf("%d%d", &n, &m)) {
        minv[0] = 0; mina[0] = 0;
        rep(i, 1, m) {
            minv[i] = minv[i - 1] + i*i*i;
            mina[i] = mina[i - 1] + 2*i*i;
        }

        if(minv[m] > n) {
            puts("0"); continue;
        }

        minArea = INF;
        area = 0;
        maxh = (n - minv[m - 1]) / (m * m) + 1;
        maxr = sqrt((n - minv[m - 1]) / m) + 1;
        dfs(n, m, maxr, maxh);

        if(minArea == INF) puts("0");
        else printf("%d\n", minArea);
    }

    return 0;
}

棋盘问题

描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

以前的代码。以前我也是给代码写注释的人呐。。。只是这种写法有点慢，现在看来应该是回溯写实在点。记录的话开两个一维数组。

#include <utility>
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int, int> P;
#define f first
#define s second

int n, k, ans;
char maze[10][10];
//存了有效点的栈
P a[100];
int pa;
//记录是否摆放
bool used[100];

bool judge(int m)
{//判断位置是否合法
    for(int i = 0; i < m; i++)
    {
        if(used[i]){
            if(a[i].s == a[m].s || a[i].f == a[m].f)
                return false;
        }
    }

    return true;
}

void dfs(int deep, int left)
{//deep是搜索的深度，left是剩余的棋子数目，也就是节点的权

    //pa - 1是栈的最后一个元素
    if(deep == pa)
        return;

    if(left == 0){
        ans++;
        return;
    }

    //剪枝，如果剩余的空格比剩余的棋子少
    if(pa - deep - 1 < left)
        return;

    dfs(deep + 1, left);

    used[deep + 1] = true;
    if(judge(deep + 1))
        dfs(deep + 1, left - 1);
    used[deep + 1] = false;
}

int main()
{
    while(cin >> n >> k && n != -1)
    {
        pa = ans = 0;
        memset(used, 0, sizeof(used));
        for(int i = 0; i < n; i++)
            cin >> maze[i];

    //把要搜的点压入栈中
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            if(maze[i][j] == '#')
                a[pa++] = P(i, j);

        if(pa < k){//剪枝
            cout << ans << endl;
            continue;
        }

        dfs(-1, k);

        cout << ans << endl;
    }

    return 0;
}