https://blog.csdn.net/weixin_44339734/article/details/104463025
遍历到某处先标记为已访问，再继续遍历下一轮，之后标记为未访问，再访问下一轮 标记为已访问放到dfs函数中去，不要在进入下一轮前在判断防止忘记主函数中设vis=true
#include <bits/stdc++.h>
using namespace std;
int X[5]={1,-1,0,0},Y[5]={0,0,1,-1},stx,sty,edx,edy;
int g[10][10],dis[10][10],tot=INT_MAX;
bool vis[10][10];
bool judge(int x,int y){
if(0<=x&&x<6&&0<=y&&y<6)return true;
else return false;
}
void dfs(int x,int y,int state,int cost){
if(vis[x][y]||cost>tot)return;
if(x==edx&&y==edy){
tot=min(tot,cost);
return;
}
vis[x][y]=true;
for(int i=0;i<4;++i){
int nx=x+X[i],ny=y+Y[i];
if(judge(nx,ny)){
int cost_now=state*g[nx][ny];
dfs(nx,ny,cost_now%4+1,cost_now+cost);
}
}
vis[x][y]=false;
}
int main() {
for(int i=0;i<6;++i){
for(int j=0;j<6;++j){
cin>>g[i][j];
}
}
cin>>stx>>sty>>edx>>edy;
dfs(stx,sty,1,0);
cout<<tot;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int g[10][10],stx,sty,edx,edy,vis[10][10],ans=INT_MAX;
int X[5]={1,-1,0,0},Y[5]={0,0,1,-1};
void dfs(int x,int y,int state,int cost){
//if(vis[x][y]||cost>ans)return;
if(cost>ans)return;
if(x==edx&&y==edy){
ans=min(ans,cost);
return;
}
//vis[x][y]=true;
for(int i=0;i<4;++i){
int nx=x+X[i],ny=y+Y[i];
if(0<=nx&&nx<6&&0<=ny&&ny<6&&!vis[nx][ny]){
vis[nx][ny]=true;
int c=g[nx][ny]*state;
dfs(nx,ny,c%4+1,cost+c);
vis[nx][ny]=false;
}
}
//vis[x][y]=false;
}
int main(){
//freopen("1.txt","r",stdin);
for(int i=0;i<6;++i){
for(int j=0;j<6;++j){
cin>>g[i][j];
}
}
cin>>stx>>sty>>edx>>edy;
vis[stx][sty]=true;
dfs(stx,sty,1,0);
cout<<ans;
return 0;
}逐行访问，使用book[i]标记第i列是否访问
#include<iostream>
#include<cstdlib>
#include<string>
#include<memory.h>
using namespace std;
int n, k;
int table[9][9];
bool book[9]; //表示第i列已经有棋子
int num , sum ;
void place(int cur){
if(num==k){
sum++;
return;
}
if(cur==n)return;
for(int j=0;j<n;++j){
if(book[j]==false&&table[cur][j]==0){
book[j]=true;
num++;
place(cur+1);
num--;
book[j]=false;
}
}
place(cur+1);//此步不能移至第22行后，否则超时
}
int main(){
while(cin>>n>>k&&n!=-1){
memset(table,0,sizeof(table));
memset(book,0,sizeof(book));
num=0;
sum=0;
string s;
for(int i=0;i<n;++i){
cin>>s;
for(int j=0;j<n;++j){
if(s[j]=='.'){
table[i][j]=1;
}
}
}
place(0);
cout<<sum<<endl;
}
return 0;
}无权图最短路径可以使用bfs（DFS容易超时，Dijkstra用来解决有权图） 图需要标记是否访问过
三维无权图最短路径
#include<iostream>
#include<cstdlib>
#include<string>
#include<memory.h>
#include<queue>
using namespace std;
int n,m,l,cnt=0,ans=-1;
char g[110][110][110];
bool vis[110][110][110];
int Dir[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } };
struct P{
int x,y,z;
};
bool judge(int x,int y,int z){
if(0<=x&&x<n&&0<=y&&y<m&&0<=z&&z<l)return true;
else return false;
}
void bfs(int x,int y,int z){
queue<P>q;
q.push({x,y,z});
while(q.size()){
cnt++;
int len=q.size();
for(int i=0;i<len;++i){
P p=q.front();
q.pop();
if(g[p.x][p.y][p.z]=='E'){
ans=cnt-1;
return;
}
for(int j=0;j<6;++j){
int x=p.x+Dir[j][0],y=p.y+Dir[j][1],z=p.z+Dir[j][2];
if(judge(x,y,z)&&g[x][y][z]!='#'&&vis[x][y][z]==false){
q.push({x,y,z});
vis[x][y][z]=true;//图需要标记是否访问过
}
}
}
}
}
int main(){
while(cin>>n>>m>>l&&n!=0){
int x,y,z;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
string s;
cin>>s;
for(int k=0;k<l;++k){
g[i][j][k]=s[k];
if(s[k]=='S'){
x=i,y=j,z=k;
}
}
}
}
cnt=0;
ans=-1;
memset(vis,0,sizeof(vis));
bfs(x,y,z);
if(ans!=-1)cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
else puts("Trapped!");
}
return 0;
}追牛的最短路径 分三个方向搜索，x+1,x-1,x*2
#include<iostream>
#include<cstdlib>
#include<string>
#include<memory.h>
#include<queue>
using namespace std;
int n,m,cnt=0,ans=-1;
int dis[100001];
void bfs(){
queue<int>q;
q.push(n);
while(q.size()){
int t = q.front();
q.pop();
int next[3];
next[0] = t + 1;
next[1] = t - 1;
next[2] = t * 2;
for (int i = 0; i < 3; i++){
if (next[i] >= 0 && next[i] <= 100000){
int d = dis[next[i]];
if (d > dis[t] + 1) {
dis[next[i]] = dis[t] + 1;
q.push(next[i]);
}
}
}
}
}
int main(){
cin>>n>>m;
if (n > m) {
printf("%d\n", n - m);
return 0;
}
memset(dis,0x3f,sizeof(dis));
dis[n]=0;
bfs();
cout<<dis[m]<<endl;
return 0;
}多源最短路
class Solution {
public:
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int n = isWater.size();
int m = isWater[0].size();
vector<vector<int>> ans(n, vector<int>(m));
queue<pair<int, int>> q;
vector<vector<bool>> isVisited(n, vector<bool>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (isWater[i][j] == 1) {
ans[i][j] = 0;
isVisited[i][j] = true;
q.push({i, j});
}
}
}
while (q.size()) {
auto v = q.front();
q.pop();
isVisited[v.first][v.second] = true;
for (int i = 0; i < 4; ++i) {
pair<int, int> now;
int nowX = v.first + dir[i][0];
int nowY = v.second + dir[i][1];
if (nowX >= 0 && nowX < n && nowY >= 0 && nowY < m && isVisited[nowX][nowY] == false) {
if (ans[nowX][nowY] == 0) {
ans[nowX][nowY] = ans[v.first][v.second] + 1;
q.push({nowX, nowY});
}
}
}
}
return ans;
}
};