Logo CloudLunar

“CodeForces/128A”的版本间的差异

（以“分类:深度优先搜索 ==摘要== {{信息题|Statues|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70200#problem/C|2|100|字母记反|4|time=2015...”为内容创建页面）
 
小 （→‎摘要： 分数）
 
第1行： 第1行：
 
[[分类:深度优先搜索]]
 
[[分类:深度优先搜索]]
 
==摘要==
 
==摘要==
−
{{信息题|Statues|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70200#problem/C|2|100|字母记反|4|time=2015-02-14 15:03:18}}
+
{{信息题|Statues|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70200#problem/C|2|100|字母记反|3|time=2015-02-14 15:03:18}}
 
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70200 Special Round for Valentine's Day] C题
 
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70200 Special Round for Valentine's Day] C题
 
*原题链接：http://codeforces.com/problemset/problem/128/A
 
*原题链接：http://codeforces.com/problemset/problem/128/A
 +
 
==题意==
 
==题意==
 
给矩阵图（左下'M'，右上'A'，很多'S'和其它空格'.'）。M、S轮流下棋，M先走。M每一步可往上下左右和四个斜方向走或不动，S每一步都向下走一格。M走到A则M获胜，中途S碰到M那么S获胜。问M是否有胜利可能。
 
给矩阵图（左下'M'，右上'A'，很多'S'和其它空格'.'）。M、S轮流下棋，M先走。M每一步可往上下左右和四个斜方向走或不动，S每一步都向下走一格。M走到A则M获胜，中途S碰到M那么S获胜。问M是否有胜利可能。

2015年2月15日 (日) 20:07的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
Statues ★★☆☆☆ 答案正确 100 2015-02-14 15:03:18 字母记反（3）

题意

给矩阵图（左下'M'，右上'A'，很多'S'和其它空格'.'）。M、S轮流下棋，M先走。M每一步可往上下左右和四个斜方向走或不动，S每一步都向下走一格。M走到A则M获胜，中途S碰到M那么S获胜。问M是否有胜利可能。

题解

搜索，S用滚动数组和二进制压位表示即可。

之所以WA是因为M和A记反了……记名字盲……调了一个小时

代码

128A.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<cmath>
  3. #define si(n) scanf("%d",&n)
  4. #define f(i,n) for(int i=1;i<=n;++i)
  5. #define ci const int &
  6. int a[30]={};
  7. int dx[9]={1,-1,0,0,1,1,-1,-1,0},
  8.     dy[9]={0,0,1,-1,1,-1,1,-1,0};
  9. inline const bool fetch(ci x,ci y,ci step=0)
  10. {
  11.     if(x>step)
  12.         return (a[x-step]>>y)&1;
  13.     else
  14.         return 0;
  15. }
  16. bool dfs(ci x,ci y,ci step=0)
  17. {
  18.     if(step>16)return 0;
  19.     if(x==1&&y==8)//fixed：结束条件//
  20.         return 1;
  21.     if(x<1||x>8||y<1||y>8)
  22.         return 0;
  23.     if(fetch(x,y,step))
  24.         return 0;
  25.     f(i,9)
  26.         if(!fetch(x+dx[i-1],y+dy[i-1],step))
  27.             if(dfs(x+dx[i-1],y+dy[i-1],step+1))
  28.                 return 1;
  29.     return 0;
  30. }
  31. int main()
  32. {
  33.     bool haveSInFirst=0;
  34.     f(i,8)
  35.     {
  36.         f(j,8)
  37.         {
  38.             char x=getchar();
  39.             if(x=='S')
  40.             {
  41.                 a[i]|=1<<j;
  42.             }
  43.         }
  44.         getchar();
  45.     }
  46.     if(dfs(8,1))//fixed:初始点错误//
  47.     {
  48.         printf("WIN");
  49.     }else{
  50.         printf("LOSE");
  51.     }
  52.     return 0;
  53. }
取自“https://blog.CloudLunar.com/index.php?title=CodeForces/128A&oldid=1129”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]