保险资料网站有哪些,深圳龙华建网站公司,网站短期电脑培训班学费,网站改版服务1562 微博转发
开始思路错误点#xff1a;在用拉链法保存关注信息的时候#xff0c;因为要看一个用户发的有多少转发的#xff0c;所以要以用户为坑位#xff0c;所有关注这个坑位的用户为链表。#xff08;开始弄反了#xff09;
e数组存某个用户的idx#xff0c;ne是…1562 微博转发
开始思路错误点在用拉链法保存关注信息的时候因为要看一个用户发的有多少转发的所以要以用户为坑位所有关注这个坑位的用户为链表。开始弄反了
e数组存某个用户的idxne是某个节点在链表上的下一个h是坑位。
st状态数组的参数是用户而不是idx
#includebits/stdc.h
using namespace std;
//1562 微博转发
const int N1e310;
int n,l;
//拉链法存储
int e[N],idx,ne[N],h[N];
bool st[N];
//e某个idx对应的用户是谁
//ne 这个用户和其他人是否被i同时关注
//h代表某个用户的关注列表的链表尾部
void add(int u,int x)
{// 把某个被关注的用户加入到某个用户的链表中e[idx]x,ne[idx]h[u],h[u]idx;
}int bfs(int s)//找某个节点的第l层关注的用户个数
{//之前都是只要有后继就加入到队列中//如何实现到规定的层的位置就终止呢//就是L层循环:每次循环都控制向外延伸一层memset(st,0,sizeof(st));queueintq;q.push(s);st[s]1;int res0;//前l层有多少个点for(int i1;il;i)//向前走l层{int numq.size();//num就是上一次循环扩展出来的点while(num--){int tq.front();q.pop();for(int jh[t];j!-1;jne[j]){if(!st[e[j]]){q.push(e[j]);res;st[e[j]]1;}}}}return res;}
int main()
{cinnl;memset(h,-1,sizeof(h));for(int i1;in;i){int x;cinx;while(x--){int u;cinu;add(u,i);//i关注了u}}int qu;cinqu;while(qu--){int user;cinuser;coutbfs(user)endl;}}//844走迷宫
自己是用pair并且second放走的步数内存超限了。
下面是自己的做法
#includebits/stdc.h
using namespace std;
//844走迷宫
typedef pairint,intPII;
typedef pairPII,int PIII;
const int N100;
int p[N][N];
int n,m;
int s[4]{0,1,0,-1};
int z[4]{1,0,-1,0};
int dfs()
{queuePIIIq;q.push({{1,1},0});while(!q.empty()){PIII tq.front();q.pop();PII zuot.first;int xzuo.first;int yzuo.second;for(int i0;i4;i){if(xz[i]1xz[i]nys[i]1ys[i]m!p[xz[i]][ys[i]]){q.push({{xz[i],ys[i]},t.second1});if(xz[i]nys[i]m){//coutt.second1endl;return t.second1;}}}}}
int main()
{cinnm;for(int i1;in;i){for(int j1;jm;j){int num;cinnum;if(num)p[i][j]1;}}cout dfs();
}
y做法直接使用一个二维数组存某个坐标到达的时候走的步数。
845 八数码
在bfs求最短路的问题中重点是怎么保存状态y的做法把矩阵转化为字符串从初始位置到这个状态走的距离就是变化的次数
太巧妙了
//看完y思路之后最后怎么都是输出不对最后找到是swap还原的那个swap应该也在if条件中就是在4层的for循环中不一定都符合不越界的要求。
#includebits/stdc.h
using namespace std;
//845 八数码
//既可以存状态又可以存步数
unordered_mapstring ,intd;//记录到这个状态转换了多少次
queuestringq;//所有的状态
string start12345678x;
int ss[4]{-1, 0, 1, 0},z[4]{0, 1, 0, -1};
int bfs(string s)
{q.push(s);d[s]0;while(q.size()){string tq.front();q.pop();int pt.find(x);int yp/3;int xp%3;int disd[t];if(tstart)return d[t];for(int i0;i4;i){// cout ********endl;int xxxz[i];int yyyss[i];//coutxx yy si::ss[i]endl;if(xx0xx3yy0yy3){swap(t[p],t[yy*3xx]);//coutyunendl;if(!d.count(t)){d[t]dis1;q.push(t);}swap(t[p],t[yy*3xx]);}//if(tstart)return d[t];}}return -1;
}int main()
{string s;for(int i0;i9;i){string c;cinc;sc;}//coutsendl;coutbfs(s)endl;}//1233全球变暖
自己做的WA先用 bfs看有几个岛屿淹没操作后再用bfs看。
#includebits/stdc.h
using namespace std;
//1233 全球变暖
typedef pairint,intPII;
const int N1010;
int n;
int p[N][N],f[N][N];
int st[N][N];
int s[4]{1,0,0,-1},z[4]{0,1,-1,0};
int bfs()
{int cnt0;memset(st,0,sizeof(st));queuePIIq;for(int i1;in;i){for(int j1;jn;j){if(!st[i][j]p[i][j])//没有被访问过的一片陆地{// coutfind that match ifendl;st[i][j]1;cnt;//coutcnt cntendl;q.push({i,j});while(q.size()){PII tq.front();//coutq.front().first q.front().secondendl;q.pop();for(int k0;k4;k){int xt.firsts[k];int yt.secondz[k];if(x1xny1ynp[x][y]!st[x][y]){q.push({x,y});st[x][y]1;}}}}}}return cnt;
}int main()
{cinn;for(int i1;in;i){for(int j1;jn;j){char c;cinc;if(c#)p[i][j]1,f[i][j]1;}}//查看有几个岛屿int precntbfs();//淹没for(int i1;in;i){for(int j1;jn;j){if(!f[i][j])//如果本来是一个海域{for(int k0;k4;k){//coutdawnendl;int xis[k];int yjz[k];if(x1xny1ynp[x][y]){p[x][y]0;//被淹没}}}}}//还有几个岛屿int poscntbfs();int numprecnt-poscnt;coutnumendl;}y是在bfs的时候就在4的for循环中判断这个连通块是否被淹没是就加加。最后根据这个连通块的节点个数和被淹没的节点个数判断这个岛屿是否被淹没
