程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HD1010 Tempter of the Bone

HD1010 Tempter of the Bone

編輯:C++入門知識

以前看杭電課件的時候,似懂非懂的把課件上的代碼打了一遍,就交上去了,然後擱置起來,不了了之,昨天飄誼童鞋在糾結這個題,就想也嘗試自己寫一遍,不寫不知道,一寫下一跳,神馬也不會,Orz……


思路:深搜+剪枝(多重剪枝)
我的AC代碼:

[cpp] 
#include<stack> 
#include<cmath> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<iostream> 
using namespace std; 
char map[9][9],step; 
bool escape; 
int e_x,e_y,s,t,dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; 
 
void DFS(int x,int y,int step1) 

    if(x<=0||y<=0||x>s||y>t)     //出界 
       return ; 
    if( escape == 1 )           //已搜到,退出 
        return ; 
    int temp=(step-step1)-abs(x-e_x)-abs(y-e_y);  //奇偶性剪枝 && 最優性剪枝 
    if(temp<0||temp&1) 
        return; 
    if(x==e_x && y==e_y)             //搜到終點 
    { 
        if(step1==step) 
            escape=1; 
        return ; 
    } 
    for(int i=0;i<4;i++){ 
        if( map[x+dir[i][0]][y+dir[i][1]] != 'X' )  //深搜 
        { 
            map[x+dir[i][0]][y+dir[i][1]]= 'X'; 
            DFS(x+dir[i][0],y+dir[i][1],step1+1); 
            map[x+dir[i][0]][y+dir[i][1]]='.'; 
        } 
    } 
    return ; 

int main(){ 
    int i,j,s_x,s_y; 
    while(~scanf("%d%d%d",&s,&t,&step),s+t+step) 
    { 
        memset(map,0,sizeof(map)); 
        for(i=1;i<=s;i++) 
        { 
            getchar(); 
            for(j=1;j<=t;j++) 
            { 
                scanf("%c",&map[i][j]); 
                if(map[i][j]=='S') 
                {   s_x=i;   s_y=j;   } 
                if(map[i][j]=='D') 
                {   e_x=i;   e_y=j;   } 
            } 
        } 
        getchar();  //這個字符問題如果最後沒有吸收,會判錯,不知道杭電是怎樣判題的 
        escape=0; 
        map[s_x][s_y]='X';               //一定要標記,否則會搜回來 
        DFS(s_x,s_y,0 ); 
        if(escape) 
                puts("YES"); 
        else 
                puts("NO"); 
    } 
    return 0; 

課件提供代碼:

[cpp] 
#include<stdio.h> 
# include <iostream> 
# include <string.h> 
# include <stdlib.h> 
using namespace std; 
char map[9][9]; 
int n,m,t,di,dj; 
bool escape; 
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; 
void dfs(int si,int sj,int cnt) 

    int i,temp; 
    if(si>n||sj>m||si<=0||sj<=0) return; 
    if(cnt==t&&si==di&&sj==dj)    escape=1; 
    if(escape) return; 
    temp=(t-cnt)-abs(si-di)-abs(sj-dj); 
    if(temp<0||temp&1) return; 
    for(i=0;i<4;i++){ 
        if(map[si+dir[i][0]][sj+dir[i][1]]!='X') 
        { 
            map[si+dir[i][0]][sj+dir[i][1]]='X'; 
            dfs(si+dir[i][0],sj+dir[i][1],cnt+1); 
            map[si+dir[i][0]][sj+dir[i][1]]='.'; 
        } 
    } 
    return; 

int main() 

    freopen("Input.txt","r",stdin); 
    freopen("Output.txt","w",stdout); 
    int i,j,si,sj; 
    while(cin>>n>>m>>t) 
    { 
      if(n==0&&m==0&&t==0) break; 
      int wall=0; 
      for(i=1;i<=n;i++) 
         for(j=1;j<=m;j++) 
         { 
            cin>>map[i][j]; 
            if(map[i][j]=='S') { si=i; sj=j; } 
            else if(map[i][j]=='D') { di=i; dj=j; } 
            else if(map[i][j]=='X') wall++; 
         } 
       if(n*m-wall<=t) 
       { 
           cout<<"NO"<<endl; 
           continue; 
       } 
       escape=0; 
       map[si][sj]='X'; 
       dfs(si,sj,0); 
       if(escape) cout<<"YES"<<endl; 
       else cout<<"NO"<<endl; 
   } 
   return 0; 

測試數據生成器:
[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<time.h> 
int main() 

    freopen("Input.txt","w",stdout); 
    int n=110; 
    srand(time(NULL)); 
    while(n--) 
    { 
    int x,y,z,i,j,temp; 
    x=rand()%6+2; 
    y=rand()%6+2; 
    z=rand()%(x*y)+1; 
    printf("%d %d %d\n",x,y,z); 
    for(i=1;i<=x;i++) 
    { 
        for(j=1;j<=y;j++) 
        { 
            if(i==x&&j==y) 
                printf("S"); 
            else if(i==x/2&&j==y/2) 
                printf("D"); 
            else 
            { 
                switch(rand()%6) 
                { 
                case 0:case 1:case 2:case 3:case 4:printf(".");break; 
                case 5:printf("X"); 
                } 
            } 
        } 
        printf("\n"); 
    } 
    } 
    return 0; 

對拍程序:
[cpp] 
#include<stdio.h> 
#include<string.h> 
int main() 

    char a[120][5],b[120][5]; 
    int i=0,j=0; 
    freopen("Output.txt","r",stdin); 
    while(~scanf("%s",a[i]))i++; 
    freopen("Output1.txt","r",stdin); 
    while(~scanf("%s",b[j]))j++; 
    for(i=0;i<j;i++) 
        if(strcmp(a[i],b[i])!=0) 
            printf("%d\n",i); 
    return 0; 

作者:ice2013

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved