A:迷宫问题
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
定义一个二维数组：
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)
1 #include<iostream>
2 #include<queue>
3 #include<cstring>
4 #include<stack>
5 using namespace std;
6 int maze[7][7]; //必须是7，不然会溢出
7 struct node{
8 int x, y, step;
9 };
10 queue<node>q;
11 bool visited[6][6];
12 int dirx[4] = {1,0,-1,0};
13 int diry[4] = {0,1,0,-1};
14 node way[6][6]; //记录每个点的父节点
15 stack<node>w; //存路径
16
17 int main(){
18 int i, j;
19 memset(maze,-1,sizeof(maze)); //可以走的路是0
20 for(i = 1; i <= 5; i++)
21 for(j = 1; j <= 5; j++){
22 cin>>maze[i][j];
23 }
24 node p; p.x = 1; p.y = 1; p.step = 0;
25 q.push(p);
26 visited[1][1] = true;
27 while(!q.empty()){
28 p = q.front();
29 q.pop();
30 if(p.x == 5 && p.y == 5){//找到终点
31 while(1){
32 w.push(p);
33 if(p.x == 1 && p.y == 1) break;
34 p = way[p.x][p.y];
35 }
36 //输出
37 while(!w.empty()){
38 p = w.top();
39 cout<<"("<<p.x-1<<", "<<p.y-1<<")"<<endl;
40 w.pop();
41 }
42 }
43 for(i = 0; i < 4; i++){
44 int nx = p.x+dirx[i];
45 int ny = p.y+diry[i];
46 if(maze[nx][ny] == 0 && !visited[nx][ny]){
47 node no;
48 no.x = nx; no.y = ny;
49 no.step = p.step+1;
50 q.push(no);
51 visited[nx][ny] = true;
52 way[nx][ny] = p;
53 }
54 }
55 }
56 return 0;
57 }
备注：这道题在博客里写过。。不知道咋用深搜做，所以就跟上次一样用广搜写的。唯一注意的一点是，可以把数组开大一点，然后memset为-1，然后从（1，1）开始输入，这样的好处是不用判断数组下标是否出界，四周都留了余量。
B:棋盘问题
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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
- 来源
- 蔡错@pku
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int n, k;
5 char board[9][9];
6 bool visited[9]; //第i列有没有棋子
7 int ans = 0;
8 void dfs(int step, int left){
9 if(left==0){
10 ans++;
11 return;
12 }
13 if(step == n ) return;
14 //if(step+left>n) return;
15 for(int i = 1; i <= n; i++){
16 if(board[step+1][i]=='#'&&!visited[i]){
17 visited[i] = true;
18 dfs(step+1, left-1);
19 visited[i] = false;
20 }
21 }
22 dfs(step+1,left); //第step+1行不放棋子
23 }
24
25 int main(){
26 while(1){
27 cin>>n>>k;
28 if(n == -1) return 0;
29 int i, j;
30 memset(board,0,sizeof(board));
31 memset(visited,0,sizeof(visited));
32 ans = 0;
33 for(i = 1; i <= n; i++)
34 for(j = 1; j <= n; j++)
35 cin>>board[i][j];
36 dfs(0, k);
37 cout<<ans<<endl;
38 }
39 return 0;
40 }
备注：这道题数据好像特别水，也不用剪枝就能过。别忘了考虑某一行可以放棋子也可以不放棋子。
C:海贼王之伟大航路
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
“我是要成为海贼王的男人！”，路飞一边喊着这样的口号，一边和他的伙伴们一起踏上了伟大航路的艰险历程。
路飞他们伟大航路行程的起点是罗格镇，终点是拉夫德鲁（那里藏匿着“唯一的大秘宝”——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!次运算，一定会超时。
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int n;
5 int island[17][17];
6 bool visited[17];
7 const int maxx = 1<<30;
8 int ans = maxx;
9 int totalen = 0; //正在走的路的长度
10 int state = 0;
11 int midl[1<<15][16];//经过状态state到达k所用的时间
12 void dfs(int cur, int step){ //当前岛屿，步数
13 if(step == n-1){ //到倒数第二个岛
14 ans = min(ans, totalen+island[cur][n]);
15 return;
16 }
17 for(int i = 2; i <= n-1; i++){
18 if(visited[i]==true) continue;
19 if(totalen+island[cur][i]>=ans) continue;
20 if(totalen+island[cur][i]>=midl[state|(1<<(i - 2))][i]) continue; //i-2是因为从2开始所以节约一点位数
21 visited[i] = true;
22 totalen += island[cur][i];
23 state|=(1<<(i - 2));
24 midl[state][i] = totalen; //这会儿肯定是最小的
25 dfs(i, step+1);
26 visited[i] = false;
27 state^=(1<<(i - 2));
28 totalen -= island[cur][i];
29 }
30 }
31
32 int main(){
33 int i, j;
34 cin>>n;
35 for(i = 1; i <= n; i++)
36 for(j = 1; j <= n; j++)
37 cin>>island[i][j];
38 for(i = 1; i < 1<<(n-1); i++)
39 for(j = 1; j <= n-1; j++)
40 midl[i][j] = maxx;
41 dfs(1, 1);
42 cout<<ans;
43 return 0;
44 }
备注：这道题就是必须用状压+剪枝才能过！也就是用Midl这个数组来记录中间状态，midl[state][k]表示在state状态下，当前位置是k的最短时间。state就是要用状态压缩，用一个整型来表示此时1-n这些地点里已经经过了哪些（包括k这个点）。最多有16个岛，掐头去尾用一个14位二进制数就可以表示，所以数组要开1<<15,因为14个岛全部经过也就是1<<15-1; 注意，左右移运算符的优先级很高，所以后面是表达式记得要加括号。state用一个全局变量来存就行，就跟visited一样是参与回溯过程的。
这个dfs可以当模板记下来。边界条件不需要走到终点，走了n-1就可以，因为最后一步肯定要走到n。剪枝的过程放在寻找下一个点的时候来进行。
注意midl的初始化！！因为i和j的范围我错了好几次。