1043 方格取数 2000年NOIP全国联赛提高组
1043 方格取数 2000年NOIP全国联赛提高组
attack
发布于 2018-04-13 12:16:24
发布于 2018-04-13 12:16:24
1043 方格取数
2000年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入描述 Input Description
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出描述 Output Description
只需输出一个整数，表示2条路径上取得的最大的和。
样例输入 Sample Input
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
样例输出 Sample Output
67
数据范围及提示 Data Size & Hint
如描述
分类标签 Tags 点此展开‘
注意ed的定义
AC：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=15;
6 int map[MAXN][MAXN];
7 int vis[MAXN][MAXN];
8 int pass[MAXN][MAXN];
9 int ans1=0;
10 int n;
11 int ed;
12 void dfs(int i,int j,int tot,int now)
13 {
14 int t=map[i][j];
15 map[i][j]=0;
16 if(i==n&&j==n)
17 {
18 if(now==1)
19 {
20 dfs(1,1,tot+ed,2);
21 }
22 else
23 {
24 if(tot>ans1)
25 ans1=tot;
26 return ;
27 }
28 }
29 vis[i][j]=1;
30 if(vis[i+1][j]==0&&i+1<=n&&j<=n&&i>0&&j>0)
31 {
32 dfs(i+1,j,tot+t,now);
33 }
34 if(vis[i][j+1]==0&&i<=n&&j+1<=n&&i>0&&j+1>0)
35 {
36 dfs(i,j+1,tot+t,now);
37 }
38 vis[i][j]=0;
39 map[i][j]=t;
40 }
41 int main()
42 {
43
44 scanf("%d",&n);
45 int x,y,z;
46 while(scanf("%d%d%d",&x,&y,&z))
47 {
48 if(x==0&&y==0&&z==0)
49 break;
50 else
51 map[x][y]=z;
52 }
53 ed=map[n][n];
54 dfs(1,1,0,1);
55 printf("%d",ans1);
56 //dfs2(1,1,0);
57 return 0;
58 }未AC：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=15;
6 int map[MAXN][MAXN];
7 int vis[MAXN][MAXN];
8 int pass[MAXN][MAXN];
9 int ans1=0;
10 int ans2=0;
11 int n;
12 int now=1;
13 void dfs(int i,int j,int tot)
14 {
15 if(i==n&&j==n)
16 {
17 if(tot>ans1)
18 {
19 memset(pass,0,sizeof(pass));
20 ans1=tot;
21 for(int i=1;i<=n;i++)
22 {
23 for(int j=1;j<=n;j++)
24 {
25 if(vis[i][j]==1)
26 pass[i][j]=1;
27 }
28 }
29 }
30 return ;
31 }
32 if(vis[i+1][j]==0&&i+1<=n&&j<=n&&i>0&&j>0)
33 {
34 vis[i+1][j]=1;
35 dfs(i+1,j,tot+map[i+1][j]);
36 vis[i+1][j]=0;
37 }
38 if(vis[i][j+1]==0&&i<=n&&j+1<=n&&i>0&&j+1>0)
39 {
40 vis[i][j+1]=1;
41 dfs(i,j+1,tot+map[i][j+1]);
42 vis[i][j+1]=0;
43 }
44 }
45 int main()
46 {
47
48 scanf("%d",&n);
49 int x,y,z;
50 while(scanf("%d%d%d",&x,&y,&z))
51 {
52 if(x==0&&y==0&&z==0)
53 break;
54 else
55 map[x][y]=z;
56 }
57 dfs(1,1,map[1][1]);
58 int tot=ans1;
59 ans1=0;
60 //printf("%d\n",tot);
61 for(int i=1;i<=n;i++)
62 {
63 for(int j=1;j<=n;j++)
64 {
65 if(pass[i][j]==1)
66 map[i][j]=0;
67 }
68 }
69 dfs(1,1,0);
70 tot=tot+ans1;
71 printf("%d",tot);
72 //dfs2(1,1,0);
73 return 0;
74 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录