CodeForces/128A

摘要

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

• 来自寒假练习：Special Round for Valentine's Day C题
• 原题链接：http://codeforces.com/problemset/problem/128/A

题意

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

题解

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

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

代码

128A.cpp代码已折叠 展开折叠内容

显示/移除行号 #include<cstdio> #include<cmath> #define si(n) scanf("%d",&n) #define f(i,n) for(int i=1;i<=n;++i) #define ci const int & int a[30]={}; int dx[9]={1,-1,0,0,1,1,-1,-1,0}, dy[9]={0,0,1,-1,1,-1,1,-1,0}; inline const bool fetch(ci x,ci y,ci step=0) { if(x>step) return (a[x-step]>>y)&1; else return 0; } bool dfs(ci x,ci y,ci step=0) { if(step>16)return 0; if(x==1&&y==8)//fixed：结束条件// return 1; if(x<1||x>8||y<1||y>8) return 0; if(fetch(x,y,step)) return 0; f(i,9) if(!fetch(x+dx[i-1],y+dy[i-1],step)) if(dfs(x+dx[i-1],y+dy[i-1],step+1)) return 1; return 0; } int main() { bool haveSInFirst=0; f(i,8) { f(j,8) { char x=getchar(); if(x=='S') { a[i]|=1<<j; } } getchar(); } if(dfs(8,1))//fixed:初始点错误// { printf("WIN"); }else{ printf("LOSE"); } return 0; }