|
??????? 这两天学了深搜，还没学完，发现了一个很严重的问题——我自己写不出题来。。。有时候有思路，但无从下手，有的时候也没有思路，看题解都要看上好一阵子。这就是自己做题少的后果吗？以前没打有时间练，几乎浪费了一年，现在要需要花更多的时间来补了。。。
hdu1175
????????一开始想复杂了，又弄结构体又弄啥的最后也没解出来，最后看的题解思路才开始通顺起来。难点是判断线路转折的次数，而且对递归不是很熟练，看了题解才有点明白，另外，return的返回条件尽量写碎一点，全括到一块竟然不判我对！？？
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,m,q,x1,x2,y3,y2,t;
bool flag,vis[maxx][maxx];
int a[maxx][maxx];
int dir[4][3]{{-1,0},{0,-1},{1,0},{0,1}};
void dfs(int x,int y,int di,int t){//t是线路转折的次数
if(flag) return;
if(t>2) return;
if(x==x2&&y==y2&&a[x][y]==a[x2][y2]){
flag=1;
return;
}
if(!(x>=1&&x<=n&&y>=1&&y<=m)) {return;}
if(t==2){//剪枝，当转折次数为2时，那么该线路以后就只能走一个方向且不能回头
if(!((di==0&&x>x2&&y==y2)||(di==1&&x==x2&&y>y2)||(di==2&&x<x2&&y==y2)||(di==3&&x==x2&&y<y2)))
return;
}
if(a[x][y]!=0) return;
if(vis[x][y]) return;
vis[x][y]=1;
for(int i=0;i<4;i++){//进行递归
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(di!=i) dfs(xx,yy,i,t+1);
else dfs(xx,yy,i,t);
}
vis[x][y]=0;//搜完了要恢复为初始状态，因为每一个判断都是独立的
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n>>m&&n&&m){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int q;
cin>>q;
for(int j=1;j<=q;j++){
cin>>x1>>y3>>x2>>y2;
if(x1==x2&&y3==y2&&a[x1][y3]!=0){
cout<<"NO"<<endl;
continue;
}
if(a[x1][y3]==a[x2][y2]&&a[x1][y3]!=0){
flag=0;
memset(vis,0,sizeof vis);
for(int i=0;i<4;i++){
int nx=x1+dir[i][0];
int ny=y3+dir[i][1];
dfs(nx,ny,i,0);
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else cout<<"NO"<<endl;
}
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
hdu5113
????????这题也是老是把初始化想得过于麻烦，递归条件还是不大会写，这题的思路就是从第一个方格开始涂色然后递归判断即可，最后还是看的题解才明白要咋写递归，这题竟然还卡空格的输出，找这个错误找了一个小时多，要不是看着题解的输出，估计这辈子也不一定能过，离谱
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,m,k,col[27],a[7][7];
bool flag;
int dir[4][3]{{-1,0},{0,-1},{1,0},{0,1}};
void input(){
scanf("%d%d%d", &n, &m, &k);
memset(a, 0, sizeof(a));
for(int i=1; i<=k; i++)
scanf("%d", &col[i]);
}
void output(){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(j!=1) printf(" ");
printf("%d", a[i][j]);
}
printf("\n");
}
}
void dfs(int x,int y,int cnt){//t是线路转折的次数
if(cnt==0){ flag=true; return;}
// cout<<"haha"<<endl;
for(int i=1;i<=k;i++)
if((cnt+1)/2<col[i])
return;
for(int i=1;i<=k;i++){
if(col[i]&&a[x-1][y]!=i&&a[x][y-1]!=i){
a[x][y]=i;
col[i]--;
if(y>=m)
dfs(x+1,1,cnt-1);
else dfs(x,y+1,cnt-1);
if(flag) return;
a[x][y]=0;
col[i]++;
}
}
return;
}
int main(){
//freopen("in.txt","r",stdin);
int tt=1,t;
cin>>t;
while(t--){
memset(a,0,sizeof(a));
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
cin>>col[i];
flag=0;
dfs(1,1,n*m);
cout<<"Case #"<<tt++<<":"<<endl;
if(!flag) cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j!=1)cout<<" ";
cout<<a[i][j];
}
cout<<endl;
}
}
}
/* input();
printf("Case #%d:\n", tt++);
flag = false, dfs(1, 1, n*m);
if(!flag)
printf("NO\n");
else{
printf("YES\n");
output();
}*/
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
poj2531
????????题意：一个n*n的矩阵，a[i][j]==a[j][i],a[ii]=0,分成n个个体，这n个个体要化为A，B
两组，求A，B两组所构成的最大权能，也就是最大数（比如n==3时，最大就是1，3为一组，2为一组，这样就有啊a[1][2]+a[2][3]是最大的）。
????????这题的题意好难理解（英语垃圾。。），还有个难点是要遍历到所有分配方案，看的题解，花了好半天才看懂思路（其实最后把数据带进去试试就差不多了，啊啊啊，我这榆木脑袋！）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,a[23][23],vis[23],ans;
void dfs(int id,int data){//这样的分法可以遍历到所有方案，具体原理我还不大懂
vis[id]=1;
int tmp=data;
for(int i=1;i<=n;i++){
if(vis[i]==0)
tmp+=a[i][id];
else tmp-=a[i][id];
}
// vis[id]=0;
ans=max(tmp,ans);
for(int i=id+1;i<=n;i++){
if(tmp>data){
dfs(i,tmp);
vis[i]=0;
}
}
}
int main(){
//freopen("in.txt","r",stdin);
while(cin>>n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
ans=0;
memset(vis,0,sizeof vis);
dfs(1,0);
cout<<ans<<endl;
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
|