//DPS(深度搜索)
//n-皇后问题
//方法一(与数字全排列相似)
#include<bits/stdc++.h>
using namespace std;
const int N = 80;
int n,res=0;
char Q[N][N];
bool cow[N],dg[N],rdg[N];//dg,rdg是对角线和反对角线,cow是列;
void dfs(int u)
{
if(u==n)
{
res++;
for(int i=0;i<n;i++) puts(Q[i]);
cout<<endl;
return;
}
for(int i=0;i<n;i++)
if(!cow[i]&&!dg[u+i]&&!rdg[n-u+i])//u+i是,根据对角线规律,每个对角线的点都等于行数+上列数.n-u+i是防止i-u为负数;
{
Q[u][i]='Q';
cow[i]=dg[u+i]=rdg[n-u+i]=true;
dfs(u+1);
Q[u][i]='.';
cow[i]=dg[u+i]=rdg[n-u+i]=false;//恢复现场
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
Q[i][j]='.';
dfs(0);//从第0行开始;
cout<<res;
}
//方法二 原始方法,通俗易懂,全局搜索
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
char Q[N][N];
bool cow[N],dg[N],rdg[N],row[N];//cow 列,row 行;
void dfs(int x,int y,int q)
{
if(y==n) y=0,x++;
if(x==n)
{
if(q==n)
{
for(int i=0;i<n;i++) puts(Q[i]);
cout<<endl;
}
return;
}
// 不放皇后
dfs(x,y+1,q);
// 放皇后
if(!cow[y]&&!row[x]&&!dg[x+y]&&!rdg[x-y+n])
{
Q[x][y]='Q';
cow[y]=row[x]=dg[x+y]=rdg[x-y+n]=true;
dfs(x,y+1,q+1);
cow[y]=row[x]=dg[x+y]=rdg[x-y+n]=false;
Q[x][y]='.';
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
Q[i][j]='.';
dfs(0,0,0);//行,列,已经放置的皇后数目;
return 0;
}
//BFS(最短路径)
//例题链接:https://vjudge.net/problem/POJ-3984;
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
typedef pair<int,int> PII;
PII q[N*N],p[N][N];
int bfs()
{
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
q[0]={0,0};
memset(d,-1,sizeof d);
d[0][0]=0;
int tt=0,hh=0;
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x<n&&x>=0&&y<m&&y>=0&&d[x][y]==-1&&g[x][y]==0)
{
d[x][y]=d[t.first][t.second]+1;
p[x][y]=t;
q[++tt]={x,y};
}
}
}
int x=n-1,y=m-1;
while(x||y)
{
cout<<x<<","<<y<<endl;
auto t=p[x][y];
x=t.first;
y=t.second;
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs()<<endl;
return 0;
}
//方法二,stl((队列方法),基本思想,步骤与方法一相同.记录下所有空格的最短路径,然后输出所需空格的最短路径.
#include<bits/stdc++.h>
using namespace std;
int mp[5][5],vis[5][5];//map记录地图,vis记录这一点是否被访问过
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//向右，向左，向上，向下移动
struct node{
int x,y;//记录点的坐标
};
node pre[10][10];//记录某个节点的父节点
void BFS()
{
queue<node> que;//STL queue的应用
node str;
str.x=str.y=0;
que.push(str);//（0，0）入队
vis[0][0]=1;//标记（0，0）已被访问
while(!que.empty())//队列不空时
{
node now=que.front();//用一个结点记录队首结点
que.pop();//出队
if(now.x==4&&now.y==4)//当前 访问的结点为（4，4），即全部访问完
return;
for(int i=0;i<4;i++)
{
node next;
next.x=now.x+dir[i][0];//x往左或者往右移动
next.y=now.y+dir[i][1];//y往上或者往下移动
if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&mp[next.x][next.y]==0&&vis[next.x][next.y]==0)
//点next(x,y)在地图里，且地图里所对应的点是路而不是墙壁，且该点未被访问
{
vis[next.x][next.y]=1;//标记为已访问
que.push(next);//下一个结点入队
pre[next.x][next.y]=now;//记录一下next（next.x,next.y）这个结点的父节点是now
}
}
}
}
void print(node cur)//倒序输出
{
if(cur.x==0&&cur.y==0)
{
printf("(0, 0)\n");
return;
}
print(pre[cur.x][cur.y]); //递归输出这个结点父节点 ，最终的结果先输出（0，0）
printf("(%d, %d)\n",cur.x,cur.y);//打印这个结点的坐标
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&mp[i][j]);
BFS();
node ed;
ed.x=ed.y=4;//定义结点ed是图的最右下角那个结点
print(ed);
return 0;
}
///朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
///时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);//将每个点每个距离赋值为无穷大
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
cout<<t<<endl;
}
///堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
///时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int h[N],e[N],ne[N],idx,n,m,w[N];
int dist[N];
bool st[N];
typedef pair<int ,int>PII;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;/// 邻接表存储所有边
}
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;//创立小根堆
heap.push({0,1});/// first存储距离，second存储节点编号
while(!heap.empty())
{
auto t=heap.top();
heap.pop();
int ver=t.second,dis=t.first;
if(st[ver]) continue;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dis+w[i])
{
dist[j]=dis+w[i];
heap.push({dist[j],j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=dijkstra();
cout<<t<<endl;
}
///最短路计数,使用邻接表动态数组,bfs
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,mod=100003;
vector<int> g[N];
int dist[N];
bool vis[N];
int cnt[N];
int n,m;
void bfs()
{
memset(dist,0x3f3f3f,sizeof dist);
memset(vis,false,sizeof vis);
queue<int>que;
dist[1]=0;
cnt[1]=1;
que.push(1);
while(!que.empty())
{
int u=que.front();
que.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto v:g[u])
{
if(!vis[v])
{
if(dist[v]>dist[u]+1)///如果此时不是1最短路,更新最短路
{
dist[v]=dist[u]+1;
cnt[v]=cnt[u];
cnt[v]%=mod;
que.push(v);
}
else if(dist[v]==dist[u]+1)///如果走的路是最短路,就在这个地方加上1;
{
cnt[v]+=cnt[u];
cnt[v]%=mod;
}
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);///储存邻接表
g[b].push_back(a);
}
bfs();
for(int i=1;i<=n;i++)
cout<<cnt[i]<<endl;
return 0;
}
///ballman-ford
///存在负边时使用
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,k;
int dist[N],backup[N];
struct node
{
int a,b,w;
}edge[N];
int ballman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof dist);
for(int j=0;j<m;j++)
{
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
int t =ballman_ford();
if(t==-1) puts("impossible");
else cout<<t<<endl;
return 0;
}
///SPFA路径
///使用的邻接表储存
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int>que;
que.push(1);
st[1]=true;
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;
for(int i=h[now];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[now]+w[i])
{
dist[j]=dist[now]+w[i];
if(!st[j])
{
que.push(j);
st[j]=true;
}
}
}
}
if(dist[n]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=spfa();
if(t==-1) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}
///二维数组存SPFA
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node
{
int b,w;
}e;
int n,m;
int dist[N];
bool st[N];
vector<node>g[N];
int spfa()
{
memset(dist,0x3f3f,sizeof dist);
dist[1]=0;
queue<int>que;
que.push(1);
st[1]=true;///表示我们的这个点已经入队列了
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;///队头出去了,那就是这个点不在这个队列里了标记false;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].b;
if(dist[v]>dist[now]+g[now][i].w)
{
dist[v]=dist[now]+g[now][i].w;
if(!st[v])///如果队列里面没有他,再加入队列;
{
st[v]=true;
que.push(v);
}
}
}
}
if(dist[n]>0x3f3f/2) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a;
cin>>a>>e.b>>e.w;
g[a].push_back(e);///存入数据
}
int t=spfa();
if(t==-1) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}
///SPFA判断负环
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node
{
int b,w;
}e;
int n,m;
int dist[N],cnt[N];
bool st[N];
vector<node>g[N];
bool spfa()
{
queue<int>que;
for(int i=1;i<=n;i++)///有可能从起点1,走不到负环的位置,所以1只需要把所有点都加入队列遍历即可
{
st[i]=true;
que.push(i);
}
while(!que.empty())
{
int now=que.front();
que.pop();
st[now]=false;///队头出去了,那就是这个点不在这个队列里了标记false;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].b;
if(dist[v]>dist[now]+g[now][i].w)
{
dist[v]=dist[now]+g[now][i].w;
cnt[v]=cnt[now]+1;///这个代表的是当前这条路的边数
if(cnt[v]>=n) return true;///如果,我是说如果当前路的边数已经大于n了,那很明显存在负环;
if(!st[v])///如果队列里面没有他,再加入队列;
{
st[v]=true;
que.push(v);
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a;
cin>>a>>e.b>>e.w;
g[a].push_back(e);///存入数据
}
if(spfa()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
///floyd算法,适用于多个询问,复杂度0n3
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k;
int d[N][N];
void floyd()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int x=1;x<=n;x++)
d[j][x]=min(d[j][x],d[j][i]+d[i][x]);
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) d[i][j]=0;
else d[i][j]=1e9;
while(m--)
{
int a,b,w;
cin>>a>>b>>w;
d[a][b]=min(d[a][b],w);
}
floyd();
while(k--)
{
int a,b;
cin>>a>>b;
if(d[a][b]>1e9/2) cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}
return 0;
}
///A-star搜索
///将bfs中的队列换成优先队列
///dist数组里除了存真实距离之外还需要存入估价距离
///3个小时理解+学新东西,要清楚这里面的估价距离是怎么算出来的,要知道哈希图函数的应用.
///此题为八数码难题,下面附上代码,下一个还有传统bfs,也是用到了哈希图;
#include<bits/stdc++.h>
//#define first x;
//#define second y;
using namespace std;
typedef pair<int,string>pis;
int f(string state)
{
int res=0;
for(int i=0;i<state.size();i++)
if(state[i]!='x')
{
int t=state[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
return res;
}
string bfs(string start)
{
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char op[]="urdl";
string end="12345678x";
unordered_map<string,int >dist;
unordered_map<string,pair<char,string>> prev;
priority_queue<pis,vector<pis>,greater<pis>>heap;
dist[start]=0;
heap.push({f(start),start});
while(!heap.empty())
{
auto t=heap.top();
heap.pop();
string state=t.second;
if(state==end) break;
int x,y;
for(int i=0;i<9;i++)
if(state[i]=='x')
{
x=i/3,y=i%3;
break;
}
string source=state;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=3||b<0||b>=3) continue;
state=source;
swap(state[x*3+y],state[a*3+b]);
if(!dist.count(state)||dist[state]>dist[source]+1)
{
dist[state]=dist[source]+1;
prev[state]={op[i],source};
heap.push({dist[state]+f(state),state});
}
}
}
string res;
while(end!=start)
{
res+=prev[end].first;
end=prev[end].second;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
string start,seq;
char c;
for(int i=0;i<9;i++)
{
cin>>c;
start+=c;
if(c!='x') seq+=c;
}
int num=0;
for(int i=0;i<8;i++)
for(int j=i;j<8;j++)
if(seq[i]>seq[j]) num++;
if(num%2) cout<<"unsolvable";
else cout<<bfs(start)<<endl;
return 0;
}
///传统bfs
///相较于A-star算法较为简便,但哈希图的搜索导致搜索时间大大减小
#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char op[]="durl";
string ed="12345678x";
unordered_map<string,int>dist;
unordered_map<string,string>pre;
bool bfs(string s)
{
queue<string>que;
que.push(s);
dist[s]=0;
while(!que.empty())
{
string t=que.front();
que.pop();
string now=t;///由于后面t中x的位置要变换,所有要开一个copy,用于记录t变换后,t之前的模样,一对一的hash;
if(t==ed) return true;
int k=t.find('x');///找到x的位置,进行操作
int x=k/3,y=k%3;///将一维的位置转换到二维
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=3||b<0||b>=3) continue;///不满足直接出局
swap(t[k],t[a*3+b]);///进行转换
if(!dist.count(t))///如果此时这个状态没被记录过,那就记录,如果被记录过,那就证明这条路肯定不是最短的次数,就直接跳过
{
dist[t]=i;///一对一hash,记录操作
pre[t]=now;///一对一hash,记录变换前的string模样
que.push(t);
}
swap(t[k],t[a*3+b]);
}
}
return false;
}
int main()
{
string st,res;
for(int i=0;i<9;i++)
{
char c;
cin>>c;
st+=c;
}
if(bfs(st))///类似于小木棍问题,将搜索问题转化为bool函数
{
string t=ed;
while(t!=st)
{
res=res+op[dist[t]];///记住,这里string类的+=与+算法不一样,所以在字符串拼接的时候最好不用+=,+=返回的是char类型,char类型不能想加
///详见:https://blog.csdn.net/weixin_43222324/article/details/106814953?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168378661516800222855326%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168378661516800222855326&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-106814953-null-null.142^v86^control,239^v2^insert_chatgpt&utm_term=%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%2B%3D%E4%B8%8E%2B&spm=1018.2226.3001.4187
t=pre[t];
}
reverse(res.begin(),res.end());///由于是从尾到头,所以要逆序一下
cout<<res;
}
else
cout<<"unsolvable";
return 0;
}
///染色法搜索
//https://www.luogu.com.cn/record/110255899
///这种包围类型的染色类型,可以通过在本题圈外面加一圈可以被搜的点,这样就可以搜到所有可以被搜的点了
///拿此题来说明,在外面加一层0,即使边是*也能也能搜到0;详细思路在https://www.luogu.com.cn/problem/P1162
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m,res;
char mp[N][N];
bool vis[N][N];
void dfs(int x,int y)///进行染色
{
if(x<0||x>n+1||y<0||y>m+1||vis[x][y]) return;///如果这个点被染过或者这个点本来就是墙,就跳过
vis[x][y]=true;
for(int i=0;i<4;i++)
dfs(x+dx[i],y+dy[i]);
}
void dfs1(int x,int y)
{
for(int i=0;i<4;i++)
{
int x1=x+dx[i],y1=y+dy[i];
if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&!vis[x1][y1]&&mp[x1][y1]=='0')
{
res++;///每标记一个,就说明有一个存在;
vis[x1][y1]=true;
dfs(x1,y1);
}
}
return;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='*') vis[i][j]=true;
}
dfs(0,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!vis[i][j])
{
res++;
vis[i][j]=true;
dfs1(i,j);
}
cout<<res;
return 0;
}
//https://www.luogu.com.cn/problem/P1077
///记忆化搜索,已经搜过的元素标记一下不需要再搜了,可以大大提高速度;
/**
所有的记忆化搜索都可以转化为动态规划,但所有的动态规划不一定能转换成记忆化搜索 --clg;
**/
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e6+7;
int n,m,a[N],f[N][N];
int dfs(int st,int num)///返回值函数,定义为int
{
if(num>m) return 0;
if(st==n+2) return 0;
if(f[st][num]) return f[st][num];///如果这种方法已经搜过,直接返回这种方法的res就可以;
if(num==m) return 1;///如果达到,说明这种方法可以,所以+1;
int res=0;
for(int i=0;i<=a[st];i++) res=(res+dfs(st+1,i+num))%mod;
f[st][num]=res;///说明我这种情况已经全搜完啦,不用再搜啦,再看到就直接给你答案了;
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<dfs(1,0);
return 0;
}
标签：dist,int,搜索算法,st,que,return,now From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17427989.html