dfs notes
听着稻香，充满着正能量！
记住“a mod b”是a除以b的余数；34 mod 10等于4，一般而言，当其中的a是负数时，不论b的符号如何结果都是负数，但是在数学计算中却不是这样，需要谨记！
再次总结dfs，框架是这样的：
bool dfs(int i, int j)
{
if(outrange || visited) return 0;
if(search a solution) return 1;
visited i, j;
for()
{
extend to next level;
if(dfs()) return 1;
}
no visited i,j
return 0;
}
最好是先判终止条件，或者叫剪枝，然后再看解。
Wordsearch 这题有点特殊，因为先判终止条件要访问word，因此有下标，因此正好前面判断是否越界，于是找到解放到前面了
找一条骑士周游路线
bool dfs(int i, int j, int cnt)
{
if(out(i, j) || v[i][j]) return 0;
if(cnt==n*m) return 1;
v[i][j]=1;
for(int k=0;k<8;k++)
{
int ni=i+dx[k], nj=j+dy[k];
cur.push_back({ni, nj});
if(dfs(ni, nj, cnt+1)) return 1;
cur.pop_back();
}
v[i][j]=0;
return 0;
}
word search 写成这种的可能会刚好找不到出口，其实是有解的
bool dfs(int curi, int curj, int wi)
{
if(out(curi, curj) || v[curi][curj] || wi<word_.size() && b[curi][curj]!=word_[wi]) return 0;
if(wi==word_.size()) return 1;
v[curi][curj]=1;
for(int k=0;k<4;k++)
{
int nx=curi+dx[k], ny=curj+dy[k];
if(dfs(nx, ny, wi+1)) return 1;
}
v[curi][curj]=0;
return 0;
}
所以还是这样写
bool dfs(int curi, int curj, int wi)
{
if(wi==word_.size()) return 1;
if(out(curi, curj) || v[curi][curj] || b[curi][curj]!=word_[wi]) return 0;
v[curi][curj]=1;
for(int k=0;k<4;k++)
{
int nx=curi+dx[k], ny=curj+dy[k];
if(dfs(nx, ny, wi+1)) return 1;
}
v[curi][curj]=0;
return 0;
}