目录
int map[MAXN][MAXM];
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
int x = read(),y = read(),w = read();
map[x][y] = w;
}
}
//最大顶点数
const int MAXN = 100010;
// vector实现邻接表定义
vector<int> e[MAXN];
// 邻接表初始化操作
// 将起点为`i`的边链全部清空
e[i].clear();
// 增加边 i 到 j 的边
e[i].push_back(j);
// 查询边
for(int i = 0;i < n;++i)
{
for(int j = 0;j < (int)e[i].size();++j)
{
//do something
}
}const int MAXN = 1000010;
const int MAXM = 1000010;
struct edge{
int to; // 这条边的另外一个顶点
int next; // 下一条边的数组下标
}e[MAXM];
//顶点 i 的第一条边的数组下标
int head[MAXN];
memset(head,-1,sizeof(head));
//存储
inline void add(int x,int y,int id)
{
edge[id].to = y;
edge[id].next = head[x];
head[x] = id;
}
//遍历
for(int i = head[x];i != -1;i = e[i].next)
{
//do something
}void dfs(int x)
{
vis[x] = 1;
for(int i = head[x];i;i = e[i].x)
{
if(!vis[e[i].t])
{
dfs(e[i].t);
}
}
}给一n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：
输入：
8 输出：
qyizhong *yizhong
gydthkjy gy******
nwidghji n*i*****
orbzsfgz o**z****
hhgrhwth h***h***
zzzzzozo z****o**
iwdfrgng i*****n*
yyyygggg y******g输入格式：
第一行输入一个数n。(7≤n≤100)。
第二行开始输入n×n的字母矩阵。
输出格式：
突出显示单词的n×n矩阵。
输入样例#1： 复制
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa输出样例#1： 复制
*******
*******
*******
*******
*******
*******
*******输入样例#2： 复制
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg输出样例#2： 复制
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
char ss[maxn][maxn],zz[]="yizhong";
int vis[maxn][maxn];
int fuck[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
struct wahaha
{
int a,b;
}c[maxn];
void dfs_one(int n);
void dfs_tow(int x,int y,int k,int cnt,wahaha c[]);
void dfs_one(int n){
for(int i=0;i< n;++i){
for(int j=0;j< n;++j){
if(ss[i][j]=='y'){
for(int k = 0; k < 8; k++)
{
int x=i+fuck[k][0];
int y=j+fuck[k][1];
if(ss[x][y]=='i') {
dfs_tow(i,j,k,0,c);
}
}
}
}
}
}
void dfs_tow(int x,int y,int k,int cnt,wahaha c[]){
if(cnt==7) {
for(int i=0;i<7;++i){
vis[c[i].a][c[i].b]=1;
}
}
else{
int dx=x+fuck[k][0];
int dy=y+fuck[k][1];
if(cnt==6||ss[dx][dy]==zz[cnt+1]){
c[cnt].a=x;c[cnt].b=y;
dfs_tow(dx,dy,k,cnt+1,c);
}
}
}
inline void init()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%s",&ss[i]);
}
memset(vis,0,sizeof(vis));
dfs_one(n);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(vis[i][j]) printf("%c",ss[i][j]);
else printf("*");
}
printf("\n");
}
}
int main(int argc, char const *argv[])
{
init();
return 0;
}给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和
终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
1≤N,M≤5
输入格式：
【输入】
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点
坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式：
【输出】
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方
案总数。
输入样例#1： 复制
2 2 1
1 1 2 2
1 2输出样例#1： 复制
1
#include<bits/stdc++.h>
using namespace std;
int SX,SY,FX,FY;
int MAP[6][6],vis[6][6];
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int ans=0;
int n,m,t;
void dfs(int x,int y)
{
if(x==FX && y==FY)
{
ans++;
return ;
}
else
{
for(int i = 0; i <= 3; i++)
{
if(vis[x+dx[i]][y+dy[i]]==0 && MAP[x+dx[i]][y+dy[i]]==1)
{
vis[x][y]=1;
dfs(x+dx[i],y+dy[i]);
vis[x][y]=0;
}
}
}
}
inline void init()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
MAP[i][j]=1;
}
}
scanf("%d%d%d%d",&SX,&SY,&FX,&FY);
for(int i=1;i<=t;++i)
{
int x,y;
scanf("%d%d",&x,&y);
MAP[x][y]=0;
}
memset(vis,0,sizeof(vis));
dfs(SX,SY);
printf("%d",ans);
}
int main(int argc, char const *argv[])
{
init();
return 0;
}单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入格式：
输入的第一行为一个单独的整数n (n≤20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度
输入样例#1： 复制
5
at
touch
cheat
choose
tact
a输出样例#1： 复制
23
（连成的“龙”为atoucheatactactouchoose）
NOIp2000提高组第三题
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
char a[55][55],b[55];
int n,np=0,first[maxn],ans=100000,vis[maxn];
struct edge{
int to,next,w;
}E[maxn<<1];
void addedge(int u,int v,int w)
{
E[++np]=(edge){v,first[u],w};
first[u]=np;
// printf("%d %d %d\n",u,v,w);
}
void dfs(int i,int l)
{
vis[i]++;//技巧
ans=max(ans,l);
for(int p=first[i];p;p=E[p].next)
{
int j=E[p].to,w=E[p].w;
if(vis[j]==2) continue;
dfs(j,l+w);
}
vis[i]--;
}
int check(int i,int j)
{
int lenj=strlen(a[j]);
int leni=strlen(a[i]);
int ans=0;
int k;
for(k=0;k+1<min(leni,lenj);k++)
{
int ok=1;
for(int r=0;r<=k;r++)
{
if(a[i][leni-1-k+r]!=a[j][r]) {ok=0;break;}
}
if(ok){ ans=k+1;break;}
}
if(ans==0) return 0;
return lenj-ans;
}
void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",&a[i]);memcpy(a[i+n],a[i],sizeof(a[i]));
}
scanf("%s",a[2*n+1]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int w=check(i,j);
if(w) addedge(i,j,w);
}
for(int i=1;i<=n;i++)//最后一个点编号随意
{
if(a[i][0]==a[2*n+1][0]) addedge(2*n+1,i,strlen(a[i])-1);
}
}
int main()
{
init();
ans=0;
dfs(2*n+1,1);
printf("%d",ans);
return 0;
}由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 10 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1输入格式：
每组测试数据第一行一个整数n(1≤n≤30)
接下来n行，由0和1组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式：
已经填好数字2的完整方阵。
输入样例#1： 复制
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1输出样例#1： 复制
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1#include<bits/stdc++.h>
using namespace std;
int maps[100][100],mapCLON[100][100]={0};
int n,x,y;
void dfs(int x,int y)
{
if(x>n||x<1||y>n||y<1||maps[x][y]!=0)//判断是否越界
return;
maps[x][y]=1;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);//四个方向
}
inline void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>maps[i][j];
if(maps[i][j]==1) mapCLON[i][j]=-1;//b用来存原来的位置
}
int flag=0;
for(int i=1;i<=n;i++)
{
if(maps[i][1]!=1) dfs(i,1);
if(maps[i][n]!=1) dfs(i,n);//搜第i行的第一列和第n列
}
for(int i=1;i<=n;i++)
{
if(maps[1][i]!=1) dfs(1,i);
if(maps[n][i]!=1) dfs(n,i);//搜第i列的第一行和第n行
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapCLON[i][j]==-1) printf("1 ");
else if(maps[i][j]==0) printf("2 ");
else printf("0 ");
}
printf("\n");
}
}
int main()
{
init();
return 0;
}房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。
输入格式：
第一行一个数n (n<=15)
接下来每行2个实数，表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2)(x1-x2)+(y1-y2)(y1-y2))
输出格式：
一个数，表示要跑的最少距离，保留2位小数。
输入样例#1： 复制
4
1 1
1 -1
-1 1
-1 -1输出样例#1： 复制
7.41
#include<bits/stdc++.h>
using namespace std;
int n,vis[1001];
double x[100],y[20];
double dis[1001][1001];
double ans=0x3f3f3f;
inline void init()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
x[0]=0;y[0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
void dfs(int step,int now,double length)
{
if(length>ans)
return;
if(step==n)
{
ans=min(ans,length);
return;
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
vis[i]=1;
dfs(step+1,i,length+dis[now][i]);
vis[i]=0;
}
}
int main(void)
{
init();
dfs(0,0,0.0);
printf("%.2f",ans);
return 0;
}原文：https://www.cnblogs.com/Chicago/p/9929847.html