机器人的运动范围(剑指Offer-13) 题面 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ ...
Block Breaker (HDU - 6699) 题面 Given a rectangle frame of size n × m. Initially, the frame is strewn with n × m square blocks of size 1 × 1. Due to the friction with the frame and each other, the blocks are stable and will not drop. However, the blocks can be knocked down. When a block is knocked down, other remaining blocks may also drop since the friction provided by other remaining blocks may not sustain them anymore. Formally, a block will drop if it is knocked or not stable, which means that at least one of the left block and the right block has been dropped and at least one of the front block and the back block has been dropped. Especially, the frame can be regarded as a huge stable block, which means that if one block’s left is the frame, only when its right block has been dropped and at least one of the front block and the back block has been dropped can it drop. The rest situations are similar. ...
Eight II （HDU - 3567) 题面 Eight-puzzle, which is also called “Nine grids”, comes from an old game. In this game, you are given a 3 by 3 board and 8 tiles. The tiles are numbered from 1 to 8 and each covers a grid. As you see, there is a blank grid which can be represented as an ‘X’. Tiles in grids having a common edge with the blank grid can be moved into that blank grid. This operation leads to an exchange of ‘X’ with one tile. ...
Eight (HDU - 1043) 题面 The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let’s call the missing tile ‘x’; the object of the puzzle is to arrange the tiles so that they are ordered as: ...
Find a way (HDU - 2612) 题面 Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki. Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest. Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes. ...
非常可乐 (HDU - 1495) 题面 大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。 ...
Oil Deposits (HDU - 1241) 题面 The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. ...
迷宫问题 (POJ - 3984) 题面 定义一个二维数组： 1int maze[5][5] = { 2 0, 1, 0, 0, 0, 3 0, 1, 0, 1, 0, 4 0, 0, 0, 0, 0, 5 0, 1, 1, 1, 0, 6 0, 0, 0, 1, 0, 7}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 ...
Fire! (UVA - 11624) 题面 思路 先跑一次bfs求出火蔓延到每一格的时间，再以此为限制对人跑bfs求解，注意有多个起火点 代码 1using namespace std; 2typedef long long ll; 3const int inf = 0x3f3f3f3f; 4const int N = 1e3+5; 5 6char b[N][N] = {{0}}; 7bool vis[N][N] = {{0}}; 8int t[N][N] = {{0}}; 9int T, n, m, ans = 0; 10 11int dx[] = { 1, -1, 0, 0}; 12int dy[] = { 0, 0, 1, -1}; 13 14struct F { 15 int x, y; 16 int step; 17}; 18 19struct P { 20 int x, y; 21 int step; 22}; 23queue<F> f; 24 25void pre() { 26 memset(vis, 0, sizeof(vis)); 27 while(!f.empty()) { 28 F tf = f.front(); 29 f.pop(); 30 31 F nf = tf; 32 for(int i=0; i<4; i++) { 33 int x = nf.x = tf.x+dx[i]; 34 int y = nf.y = tf.y+dy[i]; 35 36 if(x<0 || x>=n || y<0 || y>=m) { 37 continue; 38 } 39 40 if(!vis[x][y] && b[x][y]=='.') { 41 nf.step = tf.step+1; 42 f.push(nf); 43 vis[x][y] = 1; 44 t[x][y] = nf.step; 45 } 46 } 47 } 48} 49 50bool bfs(int x, int y) { 51 memset(vis, 0, sizeof(vis)); 52 53 P sp; 54 sp.x = x; 55 sp.y = y; 56 sp.step = 0; 57 58 queue<P> q; 59 q.push(sp); 60 vis[x][y] = 1; 61 62 while(!q.empty()) { 63 P tp = q.front(); 64 q.pop(); 65 66 P np = tp; 67 for(int i=0; i<4; i++) { 68 int x = np.x = tp.x+dx[i]; 69 int y = np.y = tp.y+dy[i]; 70 71 if(x<0 || x>=n || y<0 || y>=m) { 72 ans = tp.step+1; 73 return true; 74 } 75 76 if(!vis[x][y] && b[x][y]=='.' && tp.step+1<t[x][y]) { 77 np.step = tp.step+1; 78 q.push(np); 79 vis[x][y] = 1; 80 } 81 } 82 } 83 return false; 84} 85 86int main(void) { 87 scanf("%d", &T); 88 for(int cs=1; cs<=T; cs++) { 89 memset(t, inf, sizeof(t)); 90 scanf("%d%d", &n, &m); 91 int x, y; 92 for(int i=0; i<n; i++) { 93 for(int j=0; j<m; j++) { 94 scanf(" %c", &b[i][j]); 95 if(b[i][j]=='F') { 96 F sf; 97 sf.x = i; 98 sf.y = j; 99 sf.step = 0; 100 t[i][j] = 0; 101 f.push(sf); 102 } else if(b[i][j]=='J') { 103 x = i; 104 y = j; 105 } 106 } 107 } 108 pre(); 109 if(bfs(x, y)) 110 printf("%d\n", ans); 111 else 112 printf("IMPOSSIBLE\n"); 113 } 114 return 0; 115}
Fire Game (FZU - 2150) 题面 Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.) ...
Pots (POJ - 3414) 题面 You are given two pots, having the volume of A and B liters respectively. The following operations can be performed: FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap; DROP(i) empty the pot i to the drain; 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. ...
Prime Path (POJ - 3126) 题面 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. ...
Find The Multiple (POJ - 1426) 题面 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. 输入 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. ...
Catch That Cow (POJ - 3278) 题面 Farmer John has been informed of the location 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 X - 1 or X + 1 in a single minute * Teleporting: FJ can move from any point X to the point 2 × X in a single minute. ...
Dungeon Master (POJ - 2251) 题面 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? ...