第十一题：
题意：给出n个点(0-n-1)，接下来n行，每行有n个数，第i行代表第i-1个数距离n个点的距离，问将这些点分为两部分，两个点集之间的权值最大值为多少。例如样例中讲0,1,2分为两部分（1，3）和（2）两部分，则最长距离为map[1][2]+map[3][2]=90。
思路：首先我们将所有的点标记为0(即所有点放在一个集合里)，然后取出一个点标记为1，我们减去他们两个之间的权值，对于不在一个集合里的点，我们加上他们之间的权值。最后的结果为最大值。
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
#defineINF 0x3f3f3f3f
#defineMAXN 1005
usingnamespace std;
intc[MAXN][MAXN],vis[MAXN],ans,n;
voiddfs(int id,int data)
{
int tmp=data;
vis[id]=1;
for(int i=1;i<=n;++i)
{
if(vis[i]==0)
tmp+=c[id][i];
else
tmp-=c[id][i];
}
ans=max(ans,tmp);
for(int i=id+1;i<=n;++i)
{
if(tmp>data)
{
dfs(i,tmp);
vis[i]=0;
}
}
}
intmain()
{
while(cin>>n)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&c[i][j]);
memset(vis,0,sizeof(vis));
ans=-INF;
dfs(1,0);
cout<<ans<<endl;
}
return 0;
}
第十四题：
题意：给出一幅图，求最小染色数可以使得相邻两点不同色。即图的着色问题。
解题思路:
1.问题模型是着色问题,枚举颜色的个数, 每次枚举看可以完成全部点的着色。
2.采用深搜,每一次当前色的种数深搜完毕就加1种直到全部点都被着色完毕, 这样从最少的开始深搜,结果出现肯定是最少的。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
usingnamespace std;
intcolor[30],color_count;
intn,flag;
intmini=999999;
boolmap[30][30];
chars[30];
boolpanduan(int dep,int c)
{
for(int i=1;i<=n;i++)
{
if(map[dep][i]&&color[i]==c)
return false;
}
return true;
}
voiddfs(int dep)
{
if (flag)
return;
if (dep==n+1)
{
mini=color_count;
flag=1;
}
for (int k=1;k<=color_count;k++)
{
if (panduan(dep,k))
{
color[dep]=k;
dfs(dep+1);
color[dep]=0;
}
}
color_count++;
color[dep]=color_count;
dfs(dep+1);
color[dep]=0;
color_count--;
}
intmain()
{
while (cin>>n&&n!=0)
{
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++)
{
getchar();
cin>>s;
int len=strlen(s);
for (int j=2;j<=len-1;j++)
map[i][s[j]-'A'+1]=true;
}
flag=0;
color_count=1;
memset(color,0,sizeof(color));
dfs(1);
if (mini==1)
cout<<mini<<""<<"channel needed."<<endl;
else
cout<<mini<<""<<"channels needed."<<endl;
}
return 0;
}
第十三题：
数独游戏，每一行，每一列，以及每相邻的九个方格里都不能有重复的数字。
#include<iostream>
#include<cstring>
usingnamespace std;
intmap[10][10],count1;
boolrow[10][10],col[10][10],cr[10][10];
structp
{
int x,y;
}point[100];
intjisuan(int i,int j)
{
return ((i-1)/3)*3+(j-1)/3;
}
intdfs(int n)
{
if(n>count1)
return 1;
for(int i=1;i<=9;i++)
if(!row[point[n].x][i] &&!col[point[n].y][i] && !cr[jisuan(point[n].x,point[n].y)][i])
{
row[point[n].x][i]=true;
col[point[n].y][i]=true;
cr[jisuan(point[n].x,point[n].y)][i]=true;
map[point[n].x][point[n].y]=i;
if(dfs(n+1))
return 1;
row[point[n].x][i]=false;
col[point[n].y][i]=false;
cr[jisuan(point[n].x,point[n].y)][i]=false;
}
return 0;
}
intmain()
{
int n,i,j;
cin>>n;
while(n--)
{
count1=0;
memset(row,false,sizeof(row));
memset(col,false,sizeof(col));
memset(cr,false,sizeof(cr));
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{
scanf(" ",&map[i][j]);
if(map[i][j])
{
row[i][map[i][j]]=true;
col[j][map[i][j]]=true;
cr[jisuan(i,j)][map[i][j]]=true;
}
else
{
count1++;
point[count1].x=i;
point[count1].y=j;
}
}
dfs(1);
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
cout<<map[i][j];
cout<<endl;
}
}
return 0;
}
第二题：
题意：给定一个迷宫，S是起点，E是终点，#是墙不可走，.可以走。先输出贴左边墙走到E的步数，再输出贴右边墙的，再输出最少走多少部能到E。 解题思路: 1. 最短路径用广搜. 2. 从左搜和从右搜,方向比较难处理. 3. 起点规定一定是在迷宫的边缘, 只要确定迷宫的4条边的情况.#include<iostream>
usingnamespace std;
intw,h;
intl,r,m;
intsi,sj,di,dj;
charas[100][100];
intbs[100][100];
intdx[4]={0,-1,0,1};
intdy[4]={-1,0,1,0};
intjudge1(int c)
{
if(c==1) return 0;
if(c==2) return 1;
if(c==3) return 2;
return 3;
}
intjudge2(int c)
{
if(c==1) return 2;
if(c==2) return 3;
if(c==3) return 0;
return 1;
}
voiddfs(int x,int y,int kd,int c,int cnt)
{
if(x<0 || y<0 || x>=h || x>=w|| as[x][y]=='#')
return ;
if(kd==1)
{
if((x==di)&&(y==dj))
{
l=cnt;
return ;
}
int T=0;
c=judge1(c);
while( T<4)
{
int xx=x+dx[c];
int yy=y+dy[c];
if(xx<0||yy<0||xx>=h||yy>=w||as[xx][yy]=='#');
else break;
++c;
c%=4;
T++;
}
dfs(x+dx[c],y+dy[c],kd,c,cnt+1);
}
if(kd==2)
{
if((x==di)&&(y==dj))
{
r=cnt;
return ;
}
int T=0;
c=judge2(c);
while(T<4)
{
int xx=x+dx[c];
int yy=y+dy[c];
if(xx<0||yy<0||xx>=h||yy>=w||as[xx][yy]=='#');
else break;
--c;
c=(c+4)%4;
T++;
}
dfs(x+dx[c],y+dy[c],kd,c,cnt+1);
}
if(kd==3)
{
if(m<=cnt||bs[x][y]<=cnt)
return;
bs[x][y]=cnt;
if((x==di)&&(y==dj))
{
m=cnt;
return;
}
int T=0;
as[x][y]='#';
c=judge2(c);
while(T<4)
{
dfs(x+dx[c],y+dy[c],kd,c,cnt+1);
++c;
c%=4;
T++;
}
}
as[x][y]='.';
}
intmain()
{
int i,j,t;
cin>>t;
while(t--)
{
cin>>w>>h;
l=r=0;
for(i=0;i<h;i++)
{
cin>>as[i];
}
for(i=0;i<h;i++)
for(j=0;j<w;j++)
{
if(as[i][j]=='S')
{
si=i;
sj=j;
}
if(as[i][j]=='E')
{
di=i;
dj=j;
}
bs[i][j]=10000;
}
dfs(si,sj,1,-1,1);
dfs(si,sj,2,-1,1);
m=l>r?r:l;
dfs(si,sj,3,-1,1);
cout<<l<<""<<r<<" "<<m<<endl;
}
}
