A - 棋盘问题
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
View Code
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1Sample Output
2 1
1 //Accepted 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 char cnt[10][10]; 7 int n,k; 8 int visited[10]; //1表示有，0表示没有 9 int sum = 0; 10 void dfs(int row, int num){ 11 if(row>n || num == k){ 12 if(num==k) 13 sum++; 14 return; 15 } 16 for(int i = 0; i<n; i++){ 17 if(visited[i] == 0 && cnt[row-1][i]=='#'){ 18 visited[i] = 1; 19 dfs(row+1,num+1); 20 visited[i] = 0; 21 } 22 } 23 dfs(row+1,num); 24 return; 25 } 26 int main(){ 27 while(scanf("%d%d",&n,&k) && n != -1 && k != -1){ 28 getchar(); 29 memset(cnt,0,sizeof(cnt)); 30 memset(visited,0,sizeof(visited)); 31 for(int i=0; i<n; i++){ 32 for(int j=0; j<n; j++){ 33 scanf("%c",&cnt[i][j]); 34 } 35 getchar(); 36 } 37 sum = 0; 38 dfs(1,0); 39 cout<<sum<<endl; 40 } 41 return 0; 42 }
B - Dungeon Master
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
View Code
View Code
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
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.
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Sample Input
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!
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0Sample Output
Escaped in 11 minute(s). Trapped!
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 #include <stdlib.h> 5 using namespace std; 6 int des[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; 7 struct node{ 8 int x; 9 int y; 10 int z; 11 int step; 12 }; 13 queue<node> s; 14 int r,l,c; 15 node e; 16 char map[41][41][41]; 17 int bfs(node n){ 18 if(s.empty()) return -1; 19 if(n.x==e.x && n.y==e.y && n.z==e.z){ 20 return n.step; 21 } 22 node t; 23 for(int i=0; i<6; i++){ 24 t=n; 25 t.x += des[i][0];//cout<<t.x<<' '; 26 t.y += des[i][1];//cout<<t.y<<' '; 27 t.z += des[i][2];//cout<<t.z<<endl; 28 if(t.x<0 || t.x>(r-1) || t.y<0 || t.z<0 || t.y>(l-1) || t.z>(c-1)) 29 continue; 30 if(map[t.x][t.y][t.z] != '#'){ 31 t.step++; 32 s.push(t); 33 map[t.x][t.y][t.z] = '#'; 34 35 } 36 37 } 38 s.pop(); 39 40 node g = s.front(); 41 bfs(g); 42 } 43 44 int main(){ 45 string temp; 46 node n; 47 while(scanf("%d%d%d",&r,&l,&c) && (r+l+c)){ 48 while(!s.empty()) 49 s.pop(); 50 for(int i=0; i<r; i++){ 51 for(int j=0; j<l; j++){ 52 for(int k=0; k<c; k++){ 53 cin>>map[i][j][k]; 54 if(map[i][j][k]=='S'){ 55 n.x = i; 56 n.y = j; 57 n.z = k; 58 n.step = 0; 59 s.push(n); 60 } 61 if(map[i][j][k] == 'E'){ 62 e.x = i; 63 e.y = j; 64 e.z = k; 65 } 66 } 67 } 68 getchar(); 69 } 70 map[n.x][n.y][n.z]='#'; 71 int w = bfs(n); 72 if(w!=-1){ 73 cout<<"Escaped in "<<w<<" minute(s)."<<endl; 74 } 75 else 76 cout<<"Trapped!"<<endl; 77 78 } 79 //system("pause"); 80 return 0; 81 }
K - 迷宫问题
定义一个二维数组：
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
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的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0Sample Output
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
这是一道bfs+路径记录的题，路径记录的方法我主要是开另外一个相同的数组地图记录，每次bfs后加入队列中的点的值++，最后从终点寻找自身的值--的点，放入stack中，最后从stack中输出。
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 #include<cstring> 5 #include<stack> 6 using namespace std; 7 int maze[5][5]; 8 int maz[5][5]; 9 int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; 10 struct node{ 11 int x,y; 12 int step; 13 }; 14 queue<node> q; 15 void bfs(node n){ 16 node t,w; 17 bool flag = false; 18 if(n.x == 4 && n.y == 4) return; 19 for(int i=0; i<4; i++){ 20 t = n; 21 t.x += dir[i][0]; 22 t.y += dir[i][1]; 23 t.step++; 24 if(t.x<0 || t.x>4 || t.y<0 || t.y>4) continue; 25 if(maze[t.x][t.y]==0){ 26 flag = true; 27 q.push(t); 28 maze[t.x][t.y] = 2; 29 maz[t.x][t.y] = t.step; 30 } 31 } 32 33 w = q.front(); 34 maze[w.x][w.y] = 1; 35 q.pop(); 36 w = q.front(); 37 bfs(w); 38 } 39 int main(){ 40 for(int i=0; i<5; i++){ 41 for(int j=0; j<5; j++){ 42 scanf("%d",&maze[i][j]); 43 maz[i][j] = false; 44 } 45 } 46 node n,t; 47 n.x = 0; 48 n.y = 0; 49 n.step = 1; 50 maz[n.x][n.y] = n.step; 51 q.push(n); 52 bfs(n); 53 int i=0,j=0; 54 55 stack<node> s; 56 n.x = 4; 57 n.y = 4; 58 s.push(n); 59 while(true){ 60 n = s.top(); 61 for(int k=0; k<4; k++){ 62 t = n; 63 t.x += dir[k][0]; 64 t.y += dir[k][1]; 65 if(t.x<0 || t.x>4 || t.y<0 || t.y>4) continue; 66 if(maz[t.x][t.y]==(maz[n.x][n.y]-1)){ 67 s.push(t); 68 break; 69 } 70 } 71 if(t.x == 0 && t.y == 0) break; 72 } 73 while(!s.empty()){ 74 cout<<"("<<s.top().x<<", "<<s.top().y<<")"<<endl; 75 s.pop(); 76 } 77 return 0; 78 }