sjtu2018-棋盘遍历问题

题意理解：若存在一种搜索路径，使起点被遍历两次，其他所有节点被遍历一次，则返回Y

大体思路：

用isvalid数组存储每个点是否被搜索过，用sum来标志棋盘还有多少点没有被搜索。

从起点开始深度优先搜索，终止条件是搜索到起点且sum==0。若搜索到非法点或者已经遍历过的点，则剪枝。

注意回溯之后的恢复现场！

在main函数中，可以提前判断：

若棋盘面积为1，则返回Y

若行数或列数为1，则返回N

C++代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
const int N=15;
bool isvalid[N][N];
int sum;//表示棋盘总数
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

bool dfs(int x,int y)
{
    if(x==0&&y==0&&sum==0) return true;//走到起点且遍历了整个棋盘

    if(x<0||x>=n||y<0||y>=m||isvalid[x][y]) return false;//走到非法点或者该点已经遍历过


    //加入搜索路径
    isvalid[x][y]=true;
    sum--;

    //向四周搜索
    for(int i=0;i<4;i++)
    {
        int newx=x+dx[i],newy=y+dy[i];
        if(dfs(newx,newy))
            return true;

    }
    //回溯之后恢复现场
    isvalid[x][y]=false;
    sum++;

    return false;//该点加入搜索路径后不能完成任务，返回false
}




int main()
{
    while(cin>>n>>m)
    {
        memset(isvalid,0,sizeof isvalid);
        sum=n*m;

        if(sum==1)//棋盘大小为1
        {
            puts("Y");
            continue;
        }

        if(n==1||m==1&&sum!=1)//棋盘只有1行或1列
        {
            puts("N");
            continue;
        }

        if(dfs(0,0))    puts("Y");

        else puts("N");
    }

    return 0;
}

奇技淫巧： 观察可以发现

• 若棋盘面积为1，则满足题意
• 若棋盘行/列值不全为奇数，也可以满足题意
• 若棋盘行/列值全为奇数，则不满足题意
• 若棋盘为行数==1||列数==1，不满足题意

则可以得到：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n,m;

int main()
{
    while(cin>>n>>m)
    {
        if(n*m==1) puts("Y");

        else if((n==1||m==1)&&n*m!=1) puts("N");

        else if(n%2&&m%2) puts("N");

        else puts("Y");
    }

    return 0;
}