银河之星(乱搞+记忆化搜索)

RogerDTZ RogerDTZ     2022-09-20     290

关键词:

 

Time Limit: 1000 ms   Memory Limit: 256 MB


Description

  

 

  

 


题解

  乍一看真的无从下手,规则一脸懵逼。

  首先看到第3个规则,每个棋子往任意方向都只能走3格。可以联想一下国际象棋四个象,2个永远在黑格,2个永远在白格。

  依照这个思路,我们只有9类位置(横坐标模3与纵坐标模3都相同的位置为同一类)。

  其中,每一类位置上的棋子可以通过规则3互达同一类位置,却永远不可能用规则3走到其他类的位置。

  如下图:(想象若干个3x3的框,左上角对齐铺满整个地图,框内位置相同的即同类位置)

  

  

  我们把同类位置的棋子数量求和一下,对应放到一个3x3的九宫格里(我们按照上图以0~8为每类位置编号)。以下就只对这个九宫格操作就可以了,比如$x$个0类的棋子越过1个8类棋子到达4类位置,我们把0的数字减$x$,把8的数字减$x$,把4的数字加$x$。

  为什么不用考虑实际上棋子的位置呢?

  根据上面标红的性质,任意同类棋子可以互达。我不需要考虑我要操作的3枚棋子具体在什么地方,只要将这3枚棋子移到三点一线,就可以进行规则2的操作了。

 

 

没完

  然而不是每三个位置都能移成三点一线的,受地图大小影响,可能会出现这种情况:

  

  比如这个案例,对于7-->8-->6的情况,我能用九宫格的数字相加减吗?7-->5-->0呢?都不行。因为实际地图上,并不存在一个786、750三点一线的地方。但是0-->6-->3、1-->7-->4、0-->7-->5都是可以用九宫格的数字进行加减操作的,因为地图的确存在这种场所可以供棋子移动过来进行操作

 

 

  那么我们预处理出那些类别的位置可以走2步互达(枚举原图的位置往八个方向走2步看看走到的是什么类别的位置)。

  考虑到棋子总数只有10,我们可以用状态压缩记录这个九宫格的状态,暴力枚举即可,用map记忆一下有没有到过这个状态。

  终止状态即:指定终点同类位置的权值为1,且其他位置权值为0.


 

 1 #include <cstdio>
 2 #include <map>
 3 #define min(a,b) (a<b?a:b)
 4 using namespace std;
 5 typedef long long ll;
 6 const int base=11,xx[8]={-1,-1,-1,0,0,1,1,1},yy[8]={-1,0,1,-1,1,-1,0,1};
 7 int k,n,m,x0,y0;
 8 int can[9][9];
 9 ll bin[10],bigsta,finsta;
10 map<ll,int> ans;
11 inline int trans(int x){return x%3;}
12 void getDirection(){
13     for(int i=0;i<9;i++)
14         for(int j=0;j<9;j++) can[i][j]=0;
15     int u,v,x,y;
16     for(int i=0;i<n;i++)
17         for(int j=0;j<m;j++){
18             u=trans(i)*3+trans(j);
19             for(int k=0;k<8;k++){
20                 x=i+xx[k]*2; y=j+yy[k]*2;        
21                 if(x<0||x>=n||y<0||y>=m) continue;
22                 v=trans(x)*3+trans(y);
23                 can[u][v]=can[v][u]=1;
24             }
25         }
26 }
27 bool dfs(ll s){
28     if(s==finsta) return true;
29     if(ans[s]) return ans[s]==1;
30     int now[3][3];
31     ll t=s;
32     for(int i=8;i>=0;i--){
33         now[i/3][i%3]=t/bin[i];
34         t%=bin[i];
35     }
36     int u,v,p,x,y,px,py;
37     for(int i=0;i<3;i++)
38         for(int j=0;j<3;j++){
39             u=i*3+j;
40             for(int k=0;k<8;k++){
41                 px=i+xx[k]; py=j+yy[k];
42                 x=i+xx[k]*2; y=j+yy[k]*2;
43                 px=(px+9)%3; py=(py+9)%3; x=(x+9)%3; y=(y+9)%3;
44                 p=px*3+py; v=x*3+y;
45                 if(!can[u][v]) continue;
46                 int delta=min(now[i][j],now[px][py]);
47                 for(int g=1;g<=delta;g++)
48                     if(dfs(s-bin[p]*g-bin[u]*g+bin[v]*g)) return true;
49             }
50         }
51     ans[s]=2;
52     return false;
53 }
54 int main(){
55     bin[0]=1;
56     for(int i=1;i<=9;i++) bin[i]=bin[i-1]*base;
57     while(~scanf("%d%d%d%d%d",&k,&n,&m,&x0,&y0)){
58         ans.clear();
59         x0=trans(x0-1); y0=trans(y0-1);
60         finsta=bin[x0*3+y0];        
61         getDirection();
62         bigsta=0;
63         for(int i=1,x,y;i<=k;i++){
64             scanf("%d%d",&x,&y);
65             x=trans(x-1); y=trans(y-1);
66             bigsta+=bin[x*3+y];
67         }
68         if(dfs(bigsta)) printf("Yes\n");
69         else printf("No\n");
70     }
71     return 0;
72 }
奇妙代码

 

银河之星(galaxy)

当时没来的及做,应该是一道不是太难的搜索题。首先,可以想到可行解的数量一定远远少于不可行解的数量;与其我们直接搜索,倒不如我们根据(x,y)构造可行解,然后判断。代码实现:1#include<map>2#include<cstdio>3#inc... 查看详情

记忆化搜索

记忆化搜素是DP的一种形式记忆化搜素是DP的一种形式 查看详情

搜索分析(dfsbfs递归记忆化搜索)

搜索分析(DFS、BFS、递归、记忆化搜索)1、线性查找在数组a[]={0,1,2,3,4,5,6,7,8,9,10}中查找1这个元素。 (1)普通搜索方法,一个循环从0到10搜索,这里略。 (2)递归(从中间向两边)1//递归一定要写成记忆化递归2#include&... 查看详情

记忆化搜索(代码片段)

记忆化搜索什么是记忆化搜索?百度百科:算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。个人理解:就是每求到一个状态就保存下来,下次再遇到这个状态直接调用即可它有什么好处... 查看详情

wenbao与记忆化搜索(代码片段)

记忆化搜索:通俗地讲就是搜索的形式,dp的思想 一些搜索难以完成,dp的动态转移方程又不好写的题,就会用到记忆化搜索,利用dp记录路径(相当于为dfs剪枝)用dfs进行模拟。。啦啦啦啦啦啦,,,,,,,,,好厉害!... 查看详情

coj1686:记忆化搜索

看了N遍才看懂题意。。。题意:给N个区间,每次能向左或向右走区间长度这么多,问能不能每次都在[0,m]这个范围内思路:爆搜是不行的。。这里把状态记录一下能剪枝很多定义:s[pos][now]=-1 查看详情

记忆化搜索游荡的奶牛

[luogu1535]游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBess 查看详情

hdu2452navymaneuvers记忆化搜索

这题目意思能忍?读了半年,乱七八糟的记忆化搜索拖拖的,dp[i][0]代表以获得最小值为目标的船以i为起点。dp[i][1]代表以获得最大值为目标的船以i为起点。接下来暴力枚举入度为0的点为起点,開始记忆化搜索,constintN=... 查看详情

poj2111milleniumleapcow(记忆化搜索)

DescriptionThecowshaverevisedtheirgameofleapcow.TheynowplayinthemiddleofahugepastureuponwhichtheyhavemarkedagridthatbearsaremarkableresemblancetoachessboardofNrowsandNcolumns(3<=N<=365). He 查看详情

记忆化搜索

滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 97249 Accepted: 36874DescriptionMichael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次... 查看详情

hdu1078记忆化搜索

FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):9499    AcceptedSubmission(s):4007ProblemDescript 查看详情

记忆化搜索hdu1331

FunctionRunFunTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):2586    AcceptedSubmission(s):1255ProblemDescription 查看详情

hdu1176免费馅饼(记忆化搜索)

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1176题意不解释了简单的记忆化搜索可以拿来练练手,注意要从pos=5开始搜索#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cma 查看详情

记忆化搜索,fatmouseandcheese

1、从gird[0][0]出发,每次的方向搜索一下,每次步数搜索一下for(i=0;i<4;i++){for(j=1;j<=k;j++){inttx=x+d[i][0]*j;intty=y+d[i][1]*j;if(tx>=0&&tx<n&&ty>=0&&ty<n&&grid[x][y]<gr 查看详情

hdu1978记忆化搜索

HowmanywaysTimeLimit:3000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):5203    AcceptedSubmission(s):3067ProblemDescription这是一 查看详情

poj1661helpjimmy(记忆化搜索)

题目链接:http://poj.org/problem?id=1661一道还可以的记忆化搜索题,主要是要想到如何设dp,记忆化搜索是避免递归过程中的重复求值,所以要得到dp必须知道如何递归由于这是个可以左右移动的所以递归过程肯定设计左右所以dp的一... 查看详情

hihocoder1338agame(记忆化搜索)

时间限制:10000ms单点时限:1000ms内存限制:256MB描述LittleHiandLittleHoareplayingagame.Thereisanintegerarrayinfrontofthem.Theytaketurns(LittleHogoesfirst)toselectanumberfromeitherthebeginningortheendofthearray.Thenumb 查看详情

poj1390blocks(记忆化搜索)

BlocksTimeLimit: 5000MS MemoryLimit: 65536KTotalSubmissions: 4318 Accepted: 1745DescriptionSomeofyoumayhaveplayedagamecalled‘Blocks‘.Therearenblocksinarow,eachboxhasacolo 查看详情