# 113彩票官网

POJ1321

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

Description

Input

Output

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;
int vis;
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;
int s_z, s_x, s_y;
int e_z, e_x, e_y;
int vis;

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 = { {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];
int cur_y = y + step[i];
int cur_z = z + step[i];
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 = {{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];
int cur_y = y + step[i];
if( flip[cur_x][cur_y])
sum ++;
}
return sum % 2;
}

int getCot(){
int sum = 0;
for(int i = 0; i < m; ++i){
if(flip[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[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 = 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;
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++

## 客服在线

QQ客服 