进阶搜索专题

题目大意：

将9*9的数独完成并输出

解题思路：

用数组row[0]~row[8]来存储1~9行中每一行当前填放数字的状态，列和小九宫格类似。其次在dfs过程中选择可填放的位置时要找当前可选择数最少的格子放，这样可以极大地减少搜索的分支

代码：

#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=9;
const int NN=3;
int row[N]; // 记录放置数的状态
int line[N];
int ge[NN][NN];
int a[N][N];
int ones[1<3
int kk;
inline int lowbit(int x) // 得到二进制最后一个1及其后面的0组成的数
{
    return x & (-x);
}

void init()
{
    kk=(1<s)
    {
        if(s[0]=='e')
            break;
        memset(row,0,sizeof(row));
        memset(line,0,sizeof(line));
        memset(ge,0,sizeof(ge));
        int num=0;
        for(int i=0,k=0; i 
POJ2676-Sudoku 
题目大意：
 
与前一题基本一样，稍作修改即可
 
解题思路：
 
略
 
代码：
 
略
 
POJ1088-滑雪 
题目大意：
 
给定二维矩阵，求最长的单调递减路线的长度
 
解题思路：
 
记忆化dfs,vis[i][j]表示从当前位置开始的最长递减长度
 
代码：
 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
const int inf=0x3f3f3f3f;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
const int N=105;
int a[N][N];
int vis[N][N];

int dfs(int y, int x)
{
    if(vis[y][x])
        return vis[y][x];
    int t=0;
    for(int i=0; i<4; i++)
    {
        int fy=y+dir[i][0];
        int fx=x+dir[i][1];
        if(fy<1 || fy>n || fx<1 || fx>m || a[fy][fx]>=a[y][x])
            continue;
        t=max(t,dfs(fy, fx));
    }
    vis[y][x]=t+1;
    return vis[y][x];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>m)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin>>a[i][j];
        int ans=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                ans=max(ans,dfs(i,j));
        cout<
 
LightOJ1139-8 Puzzle 
题目大意：
 
求解8数码问题的最少步数
 
解题思路：
 
bfs预处理所有可能出现的状态，状态可以用string来存储
 
代码：
 
#include 
#include 
#include