首页 > 其他 > 详细

洛谷—— P2049 魔术棋子

时间:2017-09-22 18:38:46      阅读:249      评论:0      收藏:0      [点我收藏+]

https://www.luogu.org/problem/show?pid=2049

题目描述

在一个M*N的魔术棋盘中,每个格子中均有一个整数,当棋子走进这个格子中,则此棋子上的数会被乘以此格子中的数。一个棋子从左上角走到右下角,只能向右或向下行动,请问此棋子走到右下角后,模(mod)K可以为几?

如以下2*3棋盘:

3 4 4

5 6 6

棋子初始数为1,开始从左上角进入棋盘,走到右下角,上图中,最后棋子上的数可能为288,432或540。所以当K = 5时,可求得最后的结果为:0,2,3。

输入输出格式

输入格式:

 

输入文件magic.in第一行为三个数,分别为M,N,K (1 ≤ M,N,K ≤ 100)以下M行,每行N个数,分别为此方阵中的数。

 

输出格式:

 

输出文件magic.out第一行为可能的结果个数

第二行为所有可能的结果(按升序输出)

 

输入输出样例

输入样例#1:
Magic.in
2 3 5
3 4 4
5 6 6
输出样例#1:
3
0 2 3


记忆化
 1 #include <cstdio>
 2 
 3 inline void read(int &x)
 4 {
 5     x=0; register char ch=getchar();
 6     for(; ch>9||ch<0; ) ch=getchar();
 7     for(; ch>=0&&ch<=9; ch=getchar()) x=x*10+ch-0;
 8 }
 9 const int N(111);
10 bool get[N][N][N],vis[N][N];
11 int n,m,k,ans,val[N][N];
12 int fx[2]={0,1};
13 int fy[2]={1,0};
14 
15 void DFS(int x,int y,int w)
16 {
17     if(get[x][y][w]) return ;
18     get[x][y][w]=1;
19     if(x==n&&y==m) { ans++; return ; }
20     for(int xx,yy,i=0; i<2; ++i)
21     {
22         xx=x+fx[i],yy=y+fy[i];
23         if(xx>0&&xx<=n&&yy>0&&yy<=m)
24         DFS(xx,yy,(w*val[xx][yy])%k);
25     }
26     return ;
27 }
28 
29 int Presist()
30 {
31     read(n),read(m),read(k);
32     for(int i=1; i<=n; ++i)
33       for(int j=1; j<=m; ++j)
34         read(val[i][j]);
35     DFS(1,1,val[1][1]);
36     printf("%d\n",ans);
37     for(int i=0; i<k; ++i)
38         if(get[n][m][i]) printf("%d ",i);
39     return 0;
40 }
41 
42 int Aptal=Presist();
43 int main(){;}

 

洛谷—— P2049 魔术棋子

原文:http://www.cnblogs.com/Shy-key/p/7576104.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!