雕像（0008）

题意

有一个8*8的矩阵，左下角有一个玩家，到达右上角即可取得胜利，有若干雕像，所有雕像每一次同时向下移动一行，到达最后一行，再往下就会掉出去并且不再出现，雕像撞到玩家游戏失败，S表示雕像，M表示玩家，A表示终点

输入

…A
…
…
…
…
.SSSSSSS
S…
M…

输出

WIN

代码

#include<bits/stdc++.h>

using namespace std;

const int N=10;

char lst[N][N];

bool dfs(int x,int y,int cnt)
{
	if((x==1&&y==8)||cnt>=8)	return true;
	else
	{
		for(int i=-1;i<=1;i++)
		{
			for(int j=-1;j<=1;j++)
			{
				int nx=x+i,ny=y+j;
				if(nx>=1&&nx<=8&&ny>=1&&ny<=8&&lst[nx-cnt][ny]!='S'&&lst[nx-cnt-1][ny]!='S')
					if(dfs(nx,ny,cnt+1))	return true;
			}
		}
	}
	
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	for(int i=1;i<=8;i++)
	{
		for(int j=1;j<=8;j++)
		{
			cin>>lst[i][j];
		}
	}
	
	bool res=dfs(8,1,0);
	string ans=res?"WIN":"LOSE";
	cout<<ans<<endl;
	
	return 0;
}

总结

1.深度优先搜索

这个东西我其实还是不太会，只知道是迭代递归，函数里面调用定义的这个函数，一直到搜索结束

2.有两种情况表示胜利

要么是坐标到达了终点，也就是

x=1,y=8;

要么是雕像全部掉出矩阵，也就是计数器大于等于8，假设雕像最开始在第一层，到第二层计数器变成1，到第八层计数器变成7，掉出去计数器变成8，所以其实就是计数器变成8，只要刚好等于8即可，大于可以不写

3.dfs函数里面的两层循环

表示的是玩家可以移动的范围，上下左右还有对角位置，还需要判断一下玩家上方是否有雕像，假设有雕像也是不可行的，但是为什么行数是nx-cnt,nx-cnt-1，我暂时也没有想清楚

4.搜索顺序

从左下角，也就是玩家的起始位置开始搜索

5.题意类似于飞机大战