思路
这道题看上去还真的挺难的
我一开始想用搜索
可是,我想了想发觉不对劲
我把n,m<=6的数据全部验算了一遍
结果
事实上,题目很简单
先说特殊样例
1.n==1&&m==1时,答案显然是Y
2.接着n==1||m==1时,但棋子走出去后,显然没有回头的路,答案应该是N
3.接着是n%2==0时,棋子可以先一直走到底,再把最后一行遍历完,再是倒数第二行,倒数第三......可以发现,棋子从倒数第一行开始的转向分别是右左右左右左右左.....只要最后是向左,就可以遍历完,即n为偶数,答案为Y
示意图:
1 2 3
4 5 6
7 8 9
10 11 12
顺序依次为:1 4 7 10 11 12 9 8 5 6 3 2 1
4.然后是m%2==0时,棋子也是先走到底,再把第二列除去第一行的棋子遍历完,接着是第三,第四,第五列(都不遍历第一行)......最后再把第一行遍历了,即可到达终点,答案为Y
示意图:
1 2 3 4
5 6 7 8
9 10 11 12
顺序依次为:1 5 9 10 6 7 11 12 8 4 3 2 1
5.最后剩下的就是无解情况,答案为N
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2;
const ll Maxn=0x3ffffff,Minm=-0x3ffffff;
ll n,m;
signed main()
{
while(cin>>n>>m)
{
if(n==1&&m==1)cout<<"Y";//情况1
else if(n==1||m==1)cout<<"N";//情况2
else if(n%2==0||m%2==0)cout<<"Y";//情况3,4
else cout<<"N";//情况5
cout<<"\n";
}
}
不理解为啥样例n==1&&m==2 答案是NO , 这个情况不应该是可以遍历完的吗, 求教
n==1或者m==1,即一条直线,此时路线完全被规定了,一到尽头就不可能返回呀
如(记0为未走,1为已走,2为返回到了起点):
00->10->11->可是此时无法返回
你可以换一种理解,同一条路不能走两次
有道理,不过现在好像改成Yes了。