294 条题解
-
0
永恒蓝军 LV 3 @ 2006-08-24 20:48:52
可以用递推
到达某点的路径数等于到达它的上,左两点的路径数之和
开两个数组
一个判断该点是否有障碍,另一个统计每点的路径数之和
数据要开大一点
用extended -
-1
/*dfs*/ #include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #include<cstring> using namespace std; long long map[100][100]; int dmx[]={1,1,-1,-1,2,2,-2,-2,0}; int dmy[]={2,-2,2,-2,1,-1,1,-1,0}; int dzx[]={1,0}; int dzy[]={0,1}; int n,m,x,y; int main() { //memset(map,1,sizeof(map)); scanf("%d%d%d%d",&n,&m,&x,&y); for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) map[i][j]=1; for(int i=0;i<9;i++) if(x+dmx[i]>=0&&y+dmy[i]>=0) map[x+dmx[i]][y+dmy[i]]=0; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { if(map[i][j]) { if(i==0&&j==0) continue; else if(i==0) map[i][j]=map[i][j-1]; else if(j==0) map[i][j]=map[i-1][j]; else map[i][j]=map[i-1][j]+map[i][j-1]; } } } printf("%lld",map[n][m]); return 0; } -
-1
动规
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX=16;
int f[MAX][MAX];
int main()
{
// freopen("pj024.in","r",stdin);
// freopen("pj024.out","w",stdout);
int a,b,x,y,i,j;
cin>>x>>y>>a>>b;
for(i=0;i<=x;i++)
for(j=0;j<=y;j++)
f[i][j]=-1;for(i=0;i<=x;i++)
f[i][0]=1;
for(i=0;i<=y;i++)
f[0][i]=1;
f[a][b]=0;
f[a-2][b+1]=0;
f[a-2][b-1]=0;
f[a-1][b+2]=0;
f[a-1][b-2]=0;
f[a+2][b+1]=0;
f[a+2][b-1]=0;
f[a+1][b+2]=0;
f[a+1][b-2]=0;for(i=0;i<=x;i++)
if(f[i][0]==0)
break;
for(j=i;j<=x;j++)
f[j][0]=0;
for(i=0;i<=y;i++)
if(f[0][i]==0)
break;
for(j=i;j<=y;j++)
f[0][j]=0;
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(f[i][j]!=0)
f[i][j]=f[i-1][j]+f[i][j-1];
cout<<f[x][y]<<endl;
// fclose(stdin);
//fclose(stdout);
return 0;
} -
-1
feidaoluoye LV 9 @ 2017-11-21 20:39:18
#include <iostream> #include<cstdlib> #include<cstdio> #include<map> #include<vector> #include<cstring> #include<algorithm> #define mod 7654321 #define FOR(i,x,y) for(i=x;i<=y;++i) #define maxa 10000+100 using namespace std; int n,m,p,q,ans = 0; struct node { int x,y; }; vector<node >v; bool check(int x,int y) { int i,j; if(x==p&&y==q) return false; FOR(i,-1,1) for(j=-2;j<=2;j+=4) if(i!=0) { int np =p+i; int nq = q+j; if(x==np&&y==nq) return false; } FOR(i,-1,1) for(j=-2;j<=2;j+=4) if(i!=0) { int np =p+j; int nq = q+i; if(x==np&&y==nq) return false; } return true; } bool check1(int x,int y) { int i; FOR(i,0,v.size()-1) if(x==v[i].x&&y==v[i].y) return false; return true; } void dfs(int x,int y) { // cout<<x<<" "<<y<<endl; if(x>n) return ; if(y>m) return ; if(x==n&&y==m) { ans++; return ; } else { if(check(x,y+1)) dfs(x,y+1); if(check(x+1,y)) dfs(x+1,y); } } int main() { cin>>n>>m>>p>>q; int np,nq; v.push_back(node{p,q}); int i,j; FOR(i,-1,1) for(j=-2;j<=2;j+=4) if(i!=0) { int np =p+i; int nq = q+j; v.push_back(node{np,nq}); np = p+j; nq = q+i; v.push_back(node{np,nq}); } /* FOR(i,0,v.size()-1) cout<<v[i].x<<" "<<v[i].y<<endl;*/ dfs(0,0); cout<<ans<<endl; } -
-1
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int xx[8]={1,2,2,1,-1,-2,-2,-1};
int yy[8]={2,1,-1,-2,-2,-1,1,2};int a[100][100];
bool vis[100][100];
int sum,m,n,mx,my;void dfs(int x,int y)
{
if (x== m && y==n) sum++;
else {
if (vis[x+1][y] && x+1<=m) dfs(x+1,y);
if (vis[x][y+1]&& y+1<=n) dfs(x,y+1);
}
}int main()
{
memset(vis,1,sizeof(vis));
cin>>m>>n;
cin>>mx>>my;
sum=0;
vis[mx][my]=0;
for (int i=0;i<8;i++)
if (mx+xx[i]>=0 && mx+xx[i]<=m && my+yy[i]>=0 && my+yy[i]<=n)
vis[mx+xx[i]][my+yy[i]]=0;
dfs(0,0);
cout<<sum<<endl;
return 0;
}-
神犇为 @ 2017-07-19 11:43:02
要超时，孩子，；年轻
-
-
-1
#include <bits/stdc++.h> using namespace std; int a[101][101]; bool flag[101][101]; void horse(int x,int y) { flag[x][y]=false; flag[x+2][y+1]=false; flag[x+1][y+2]=false; if(x-2>0)flag[x-2][y+1]=false; if(x-1>0)flag[x-1][y+2]=false; if(y-1>0)flag[x+2][y-1]=false; if(y-2>0)flag[x+1][y-2]=false; if(x-2>0&&y-1>0)flag[x-2][y-1]=false; if(x-1>0&&y-2>0)flag[x-1][y-2]=false; } int main() { memset(flag,true,sizeof(flag)); memset(a,0,sizeof(a)); int i,j,k,l,n,m,x,y; cin>>n>>m; n++,m++; cin>>y>>x; horse(++x,++y); a[1][1]=1; for(i=1;i<=m;i++) { for(j=1;j<=n;j++){ if(flag[i][j]) { a[i][j]+=a[i-1][j]+a[i][j-1]; } else a[i][j]=0; } } /*for(i=0;i<=m;i++) { for(j=0;j<=n;j++){ if(flag[i][j]) cout<<a[i][j ]<<' '; else cout<<"h "; } cout<<endl; }*/ if(flag[n][m] && (x!=1||y!=1)) cout<<a[m][n]<<endl; else cout<<"0"<<endl; return 0; } -
-1
cdqzgxxqdql LV 10 @ 2016-08-30 20:11:57
dp水题
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int map[20][20];
int main()
{
int x0,x1,y0,y1;
cin>>x0>>y0>>x1>>y1;
x1+=2;y1+=2;x0+=2;y0+=2;
map[x1][y1]=map[x1-2][y1-1]=map[x1-2][y1+1]=map[x1-1][y1+2]=map[x1-1][y1-2]=map[x1+1][y1-2]=map[x1+1][y1+2]=map[x1+2][y1-1]=map[x1+2][y1+1]=-1;
for(int i=2;i<=x0;i++)
{
if(map[i][2]!=-1)map[i][2]=1;
else break;
}
for(int i=2;i<=y0;i++)
{
if(map[2][i]!=-1)map[2][i]=1;
else break;
}for(int i=3;i<=x0;i++)
for(int j=3;j<=y0;j++)
{
if(map[i][j]==-1)continue;
if(map[i-1][j]!=-1)map[i][j]+=map[i-1][j];
if(map[i][j-1]!=-1)map[i][j]+=map[i][j-1];
}
printf("%d",map[x0][y0]);
}-
明明搜索好吗大哥
-
-
-1
秒。嘿嘿嘿
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>using namespace std;
int f[20][20];
bool check[20][20];
int m1,m2,b1,b2;void init(){
memset(check,true,sizeof(check));
memset(f,0,sizeof(f));
scanf("%d%d",&b1,&b2);
scanf("%d%d",&m1,&m2);
f[0][0] = 1;
check[m1][m2] = false;
check[m1 - 1][m2 - 2] = false;
check[m1 + 1][m2 - 2] = false;
check[m1 + 2][m2 - 1] = false;
check[m1 + 2][m2 + 1] = false;
check[m1 + 1][m2 + 2] = false;
check[m1 - 1][m2 + 2] = false;
check[m1 - 2][m2 + 1] = false;
check[m1 - 2][m2 - 1] = false;}
void solve(){
for(int i = 0;i <= b1;i ++){
for(int j = 0;j <= b2;j ++){
if(i > 0 && check[i-1][j]) f[i][j] += f[i-1][j];
if(j > 0&& check[i][j-1]) f[i][j] += f[i][j-1];
}
}
printf("%d",f[b1][b2]);
}int main(){
init();
solve();
return 0;
}
永恒蓝军
LV 3
@ 2006-08-24 20:48:52
