彩票平台:首页 > 学习之路 > ACM||算法ACM||算法

113彩票官网

卞振伟2019-04-28【ACM||算法】人已围观

简介掌握常用的搜索算法

POJ1321
棋盘问题

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 80092   Accepted: 37337

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

2
1

 

#include<string.h>
#include<stdio.h>

using namespace std;

int n, k;
char mp[10][10];
int vis[10];
int ans, cot;

void dfs(int x){
    if(cot == k){
        ans ++;
        return ;
    }
    if(x >= n)
        return ;

    for(int i = 0; i < n; ++i){
        if(!vis[i] && mp[x][i] == '#'){
            vis[i] = 1;
            cot++;
            dfs(x+1);
            vis[i] = 0;
            cot--;
        }
    }
    dfs(x+1);

}

int main(){
    while(~scanf("%d %d", &n, &k)){
        if(n == -1 || k == -1)
            return 0;
        memset(vis, 0, sizeof(vis));
        cot = 0;
        ans = 0;
        for(int i = 0; i < n; ++i){
            scanf("%s", mp[i]);
        }
        dfs(0);
        printf("%d\n",ans);
    }

    return 0;
}


POJ2251
Dungeon Master
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 57769   Accepted: 21312

Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. 

Is an escape possible? If yes, how long will it take? 

Input

The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). 
L is the number of levels making up the dungeon. 
R and C are the number of rows and columns making up the plan of each level. 
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.

Output

Each maze generates one line of output. If it is possible to reach the exit, print a line of the form 
Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape. 
If it is not possible to escape, print the line 
Trapped!

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<queue>
#include<cstring>

using namespace std;

int L, R, C;
char mp[40][40][40];
int s_z, s_x, s_y;
int e_z, e_x, e_y;
int vis[40][40][40];

struct coor{
    int x, y, z;
    int cot;
    coor(int xx, int yy, int zz, int cott){
        x = xx;
        y = yy;
        z = zz;
        cot = cott;
    }
};

int step[6][3] = { {1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1} };

bool outBorder(int x, int y, int z){
    if(x<1 || x>R || y<1 || y>C || z<1 || z>L){
        return true;
    }
    return false;
}

void bfs(){
    queue<coor> q;
    coor p(s_x, s_y, s_z, 0);
    vis[p.x][p.y][p.z] = 1;
    q.push(p);
    int res = 0;
    while(!q.empty()){
        p = q.front();
        q.pop();
        int x, y, z;
        x = p.x;
        y = p.y;
        z = p.z;
        int cot = p.cot;
        if(x == e_x && y == e_y && z == e_z){
            printf("Escaped in %d minute(s).\n", cot);
            return ;
        }
        for(int i = 0; i < 6; ++i){
            int cur_x = x + step[i][0];
            int cur_y = y + step[i][1];
            int cur_z = z + step[i][2];
            if( !outBorder(cur_x, cur_y, cur_z) && !vis[cur_x][cur_y][cur_z]
                && mp[cur_z][cur_x][cur_y] != '#'  ){
                q.push( coor(cur_x, cur_y, cur_z, cot+1) );
                vis[cur_x][cur_y][cur_z] = 1;
               // printf("%d   %d  %d  %d\n", res , x, y, z);
               // printf("%d   %d  %d  %d\n", res++ , cur_x, cur_y, cur_z);

               // printf("%c\n",mp[cur_x][cur_y][cur_z]);
                
            }
        }
    }
    printf("Trapped!\n");
}

int main(){
    while(~scanf("%d %d %d", &L, &R, &C)){
        if(L == 0 || R == 0 || C == 0)
            return 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= L; ++i){
            for(int j = 1; j <= R; ++j){
                for(int k = 1; k <= C; ++k){
                    cin >> mp[i][j][k];
                    if(mp[i][j][k] == 'S'){
                        s_z = i;
                        s_x = j;
                        s_y = k;
                    }
                    else if(mp[i][j][k] == 'E'){
                        e_z = i;
                        e_x = j;
                        e_y = k;
                    }
                }
            }
        }
        bfs();
    }
}

POJ3278
Catch That Cow
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 136382   Accepted: 42168

Description

Farmer John has been informed of the //location.href of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points - 1 or + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

const int maxn = 1e5+10;
using namespace std;
int n, k;
int d[maxn];
int vis[maxn];

void bfs(){
    queue<int> q;
    q.push(n);
    vis[n] = 1;
    if(n == k){
        cout<<0;
        return ;
    }
    int x;
    while(!q.empty()){
        x = q.front();
        q.pop();
        if( x == k ){
            cout<<d[x];
            return;
        }

        if(x+1 < maxn && !vis[x+1] ){
            q.push(x+1);
            vis[x+1] = 1;
            d[x+1] = d[x] + 1;
        }
        if( x - 1 >= 0 && !vis[x-1] ){
            q.push(x-1);
            vis[x-1] = 1;
            d[x-1] = d[x] + 1;
        }
        if(x*2 < maxn && !vis[x*2] ){
            q.push(x*2);
            vis[x*2] = 1;
            d[x*2] = d[x] + 1;
        }
    }
}


int main(){
    cin>>n>>k;
    bfs();
}

POJ3279
Fliptile
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 20634   Accepted: 7395

Description

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the //location.hrefs to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".

Input

Line 1: Two space-separated integers: M and N 
Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white

Output

Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular //location.href.

Sample Input

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Sample Output

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<queue>
#include<cstring>
#include<bitset>

using namespace std;

#define en() printf("\n")
#define sp() printf(" ")

const int maxn = 20;
int n, m, k;
int mp[maxn][maxn];
int flip[maxn][maxn];
int Min = 0x3f3f3f3f;
int ans[maxn][maxn];
int step[5][2] = {{1,0},{-1,0},{0,1},{0,-1},{0,0}};


bool isFlip(int x, int y){
    int sum = mp[x][y];
    for(int i = 0; i < 5; ++i){
        int cur_x = x + step[i][0];
        int cur_y = y + step[i][1];
        if( flip[cur_x][cur_y])
            sum ++;
    }
    return sum % 2;
}

int getCot(){
    int sum = 0;
    for(int i = 0; i < m; ++i){
        if(flip[0][i])
            sum ++;
    }

    for(int i = 1; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(isFlip(i-1, j)){
                flip[i][j] = 1;
                sum ++;
            }
        }
    }

    for(int i = 0; i < m; ++i){
        if(isFlip(n-1, i))
            return -1;
    }
    
    return sum;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j)
            scanf("%d", &mp[i][j]);
    }
    
    for(int i = 0; i < 1<<m; ++i){
        memset(flip, 0, sizeof(flip));
        for(int j = 0; j < m; ++j){
            flip[0][m-j-1] = i >> j & 1;
        }

        int cot = getCot();

        if(cot == -1)
            continue;

        if(cot < Min){
            Min = cot;
            memcpy(ans, flip, sizeof(flip));
        }
    }

    if(Min == 0x3f3f3f3f)
        printf("IMPOSSIBLE");
    else{
        for(int i = 0; i < n; ++i){
            if(i)   en();
            for(int j = 0; j < m; ++j){
                if(j)   sp();
                printf("%d", ans[i][j]);
            }
        }
    }
    return 0;
}

POJ1426
Find The Multiple
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 48234   Accepted: 20156   Special Judge

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

2
6
19
0

Sample Output

10
100100100100100100
111111111111111111
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;

#define en() printf("\n")
#define sp() printf(" ")
#define ll long long

int main(){
    queue<ll> q;
    ll n;
    while(cin >> n && n){
        while(!q.empty())
            q.pop();
        q.push(1);
        while(!q.empty()){
            ll p = q.front();
            q.pop();
            if(p % n == 0){
                cout<<p<<endl;
                break;
            }
            q.push(p*10);
            q.push(p*10+1);

        }
    }
    return 0;
}

POJ3126
Prime Path
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 32481   Accepted: 17587

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. 
— It is a matter of security to change such things every now and then, to keep the enemy in the dark. 
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! 
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. 
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! 
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. 
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime. 

Now, the minister of finance, who had been eavesdropping, intervened. 
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. 
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? 
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above. 
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<string.h>
#include<math.h>
#include<stack>

using namespace std;

#define en() printf("\n")
#define sp() printf(" ")
#define ll long long

const int maxn = 1e5+10;
int m, n;

bool prime[maxn];
void init(){
    memset(prime, 1, sizeof(prime));
    prime[1] = 0;
    for(int i = 2; i < maxn; ++i){
        for(int j = i*2; j < maxn; j += i)
            prime[j] = 0;
    }
}

int pre[maxn];
bool vis[maxn];
int d[maxn];
void bfs(){
    queue<int> q;
    q.push(n);
    vis[n] = 1;
    int p;
    while(!q.empty()){
        p = q.front();
        int t = p;
        q.pop();
        int a[4];
        if(p == m){
            return ;
        }

        for(int i = 0; i < 4; ++i){
            a[i] = p%10;
            p /= 10;
        }
        for(int i = 0; i < 10; ++i){
            for(int k = 0; k < 4; ++k){
                int tmp = t - (a[k] - i)* pow(10,k);
                if( tmp < 10000 && tmp >= 1000 && i != a[k] && !vis[tmp] && prime[tmp]){
                    q.push(tmp);
                    d[tmp] = d[t] + 1;
                    vis[tmp] = 1;
//                    pre[tmp] = t;
                }
            }
        }
    }
}

//void Print(int x){
//    stack<int> s;
//    while(pre[x]){
//        s.push(x);
//        x = pre[x];
//    }
//    while(!s.empty()){
//        printf("%d  ", s.top());
//        s.pop();
//    }
//}

int main(){
    int t;
    init();
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        memset(d, 0, sizeof(d));
        memset(vis, 0, sizeof(vis));
        bfs();
        cout<<d[m]<<endl;
//        Print(m);
    }
    return 0;
}

Tags:编程   程序员   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:71篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00