（以“分类:深度优先搜索 ==摘要== {{信息题|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|字母记反| | + | {{信息题|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是否有胜利可能。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 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;
}
|
CloudLunar