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 }
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 }