(以“分类:深度优先搜索 ==摘要== {{信息题|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代码已折叠
展开折叠内容
#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;
}

著作权声明[编辑]

关于[编辑]