首页 > 代码库 > 【记忆化搜索+优化】10411 - SKAKAVAC
【记忆化搜索+优化】10411 - SKAKAVAC
【记忆化搜索+优化】10411 - SKAKAVAC
Time Limit: 4000MS
Memory Limit: 36000KB
给定一个N-N的矩形，每个格子有一个数字，某人最初在R行C列的位置，他可以按以下规则移动：
1.跳到相邻的行，但列数差要大于1的所有格子。跳到相邻的列，位行数差要大于1的所有格子。即如果当前位置是（r1,c1）要跳到(r2,c2)则它们满足：
|r1-r2|=1且|c1-c2|>1或者|c1-c2|=1且|r1-r2|>1
2.目标格子的数字严格大于起跳格子的数字。
要求计算在这种规则下走过的最多的格子。
输入：
第一行1个整数N表示矩形的大小。(1 ≤ N ≤1500)
第二行两个数字R (1 ≤ R ≤N) 和 C (1 ≤ C ≤N)初始位置。.
接下来N行，每行N个数，表示每个格子里的数字。
输出：
一个整数表示走过的最多的格子。
注：50%的数据N小于100，80%的数据N小于1000；
样例：
输入：
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
输出：
4
输入：
5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13
输出：
21
Source
coi2008-2009-1
先上开始写的20行暴搜程序
1 # include<cmath> 2 # include<queue> 3 # include<stdio.h> 4 # include<cstring> 5 # include<iostream> 6 # include<algorithm> 7 using namespace std; 8 const int maxn=1500+50; 9 int map[maxn][maxn];10 int tot=0,n;11 queue<int>q;12 int dfs(int r1,int c1,int cur){13 for(int r2=1;r2<=n;r2++)14 for(int c2=1;c2<=n;c2++)15 if(map[r2][c2]>map[r1][c1]&&(abs(r1-r2)==1&&abs(c1-c2)>1||abs(c1-c2)==1&&abs(r1-r2)>1))16 dfs(r2,c2,cur+1);17 tot=max(tot,cur);18 }19 int main(){20 scanf("%d",&n);21 int sr,sc;scanf("%d%d",&sr,&sc);22 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);23 dfs(sr,sc,1);24 printf("%d",tot);25 return 0;26 }
然后给出50分的计划搜索
1 # include<cmath> 2 # include<stdio.h> 3 # include<algorithm> 4 using namespace std; 5 const int maxn=1500+50; 6 int map[maxn][maxn],dp[maxn][maxn]; 7 int tot=0,n; 8 int dfs(int r1,int c1){ 9 int ok=1;10 if(dp[r1][c1])return dp[r1][c1];11 for(int r2=1;r2<=n;r2++)12 for(int c2=1;c2<=n;c2++)13 if(map[r2][c2]>map[r1][c1]&&(abs(r1-r2)==1&&abs(c1-c2)>1||abs(c1-c2)==1&&abs(r1-r2)>1)){14 dp[r1][c1]=max(dp[r1][c1],dfs(r2,c2)+1);15 ok=0;16 }17 if(ok)dp[r1][c1]=1;18 return dp[r1][c1];19 }20 int main(){21 scanf("%d",&n);22 int sr,sc;scanf("%d%d",&sr,&sc);23 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);24 dfs(sr,sc);25 printf("%d",dp[sr][sc]);26 return 0;27 }
【记忆化搜索+优化】10411 - SKAKAVAC
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。