TZOJ 5296：游戏之禁酒

描述

zzx在某个游戏的副本中，要到一个迷宫里取一件物品，他只要走到物品的周围四个格子的任意一个就可以取到物品了，zzx每次可以选择走一步或者跳一步，知道了一个提示——禁酒（所有与9相关的格子都是有陷阱），经过多次试验，zzx知道了这个相关的定义——格子里的数字包含9的或者能被9整除的格子都是陷阱。

走一步：就是从中间蓝色的格子走到黄色的格子

跳一步：就是从中间蓝色的格子跳过黄色的格子，到红色的格子，即使黄色的格子是陷阱，也不算走到陷阱上

zzx知道city走迷宫比较厉害，于是就是寻找city了，但city有一个条件，必须要一定在不碰陷阱就能取得这个物品的迷宫她才肯帮忙，于是想寻求你们的帮助，判断一个这个迷宫是否一定能不碰陷阱就能到？

输入

输入有多组，输入到文件结束为止

每组的第一行，一个m,n(不超过15)，n表示有几行，m表示有几列，下面是一个n*m的矩阵，矩阵中s表示起点，w表示物品的位置，矩阵中的数字小于100位。

输出

zzx能在不碰陷阱的情况下取到物品，输出YES，否则输出NO。

样例输入

3 3
S 9 8
8 6 9
9 8 W

样例输出

YES

提示

物品格不可以走到，也就是说要取的物品必须在物品格周围的四格

题解

注意输入的是100位的数字所以要用到大数除，然后注意提示不能直接走到物品的位置。然后就是一题简单的搜索题了。

代码

#include <bits/stdc++.h>
using namespace std;
int dir[][2]={
    1,0,-1,0,0,1,0,-1,2,0,-2,0,0,2,0,-2,1,1,1,-1,-1,1,-1,-1};
bool mp[20][20];
char str[100+5];
int sx,sy,wx,wy;
bool mod()//判断大数是否能被9整除
{
    int l=strlen(str);for(int i=0;i<l;i++){
    str[i]-='0';}for(int i=0;i<l-1;i++){
    if(str[i]>=9)str[i+1]=str[i+1]+10*(str[i]%9);else{
    str[i+1]=str[i+1]+10*str[i];}}if(str[l-1]==0||str[l-1]%9==0)return 0;else return 1;
}
void pandi(int x,int y)
{
    if(str[0]=='S')sx=x,sy=y;else if(str[0]=='W')wx=x,wy=y;else{
    if(mod())mp[x][y]=0;else mp[x][y]=1;}
}
bool flog;
int n,m;
void dfs(int x,int y)
{
    if(abs(x-wx)+abs(y-wy)==1){
    flog=1;return;}for(int i=0;i<12;i++){
    int dx=x+dir[i][0];int dy=y+dir[i][1];if(mp[dx][dy]==0&&dx>=1&&dy>=1&&dx<=n&&dy<=m){
    mp[dx][dy]=1;dfs(dx,dy);}}
}
int main()
{
    while(~scanf("%d %d",&m,&n)){
    flog=0;memset(mp,1,sizeof(mp));for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    scanf("%s",str);pandi(i,j);}}mp[sx][sy]=1;dfs(sx,sy);if(flog)printf("YES\n");else printf("NO\n");   }}