查看CodeForces/128A的源代码 ←CodeForces/128A

[[分类:深度优先搜索]]
==摘要==
{{信息题|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://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代码已折叠
|<pre>
#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;
}
</pre>
|code128A}}