nyoj92 图像有用区域

这题其实不难，就是一个bfs；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<stdio.h>  
#include<stdlib.h>  
#include<queue>  
using namespace std;  
int map[965][1445];  
int dir[4][2]={1,0,  0,1,  -1,0,  0,-1};  
typedef struct Point  
{  
    int x,y;  
}P;  
queue<P> Q;  
int w,h;  
int main()  
{  
//  freopen("d:\\data\\1.txt","r",stdin);  
    void bfs();  
    int ncase;  
    int i,j;  
    P tt;  
    scanf("%d",&ncase);  
    while(ncase--)  
    {  
        scanf("%d%d",&w,&h);  
        for(i=0;i<h;i++)  
        {  
            for(j=0;j<w;j++)  
            {  
                scanf("%d",&map[i][j]);  
                if((i==0 || j==0 || i==(h-1) || j==(w-1) )&& map[i][j]!=0)  
                {  
                    tt.x=j;  
                    tt.y=i;  
                    map[i][j]=0;  
                    Q.push(tt);  
                }  
            }  
        }  
        bfs();  
        for(i=0;i<h;i++)  
        {  
            for(j=0;j<w;j++)  
                printf("%d ",map[i][j]);  
            printf("\n");  
        }  
    }  
    return 0;  
}  
void bfs()  
{  
      
    P cur,next;  
    while(!Q.empty())  
    {  
        int k;  
        cur=Q.front();  
        Q.pop();  
        for(k=0;k<4;k++)  
        {  
            next.x=cur.x+dir[k][0];  
            next.y=cur.y+dir[k][1];  
            if(next.x>=0 && next.x<w && next.y>=0 && next.y<h && map[next.y][next.x]!=0)  
            {  
                map[next.y][next.x]=0;  
                Q.push(next);  
            }  
        }  
    }  
      
    while(!Q.empty())  
        Q.pop();  
    return ;  
}

上面的代码不不需要讲了吧，只要你会bfs你就会做，但是注意这题有个坑，就是他说的长度和高度，我之前提交几次，就是被这个坑了，其实自习看看还是怪自己粗心大意，
好好看题，养成好习惯，对以后的工作生活都有好处。

nyoj114 某种序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>  
#include<string.h>  
#define base  10000  
int a[100][100];  
void t(int i,int n)  
{  
    int j=1;  
    do  
    {  
        a[i][j++]=n%base;  
        n/=base;  
    }while(n);  
}  
int main()  
{  
    //freopen("d:\\data\\1.txt","r",stdin);  
    int i,j,len,t1,t2,t3,temp,jw;  
    while(scanf("%d%d%d",&t1,&t2,&t3)!=EOF)  
    {  
        if(t1==0 && t2==0 && t3==0)  
            printf("0");  
        else  
        {  
            memset(a,0,sizeof(a));  
            t(0,t1);  
            t(1,t2);  
            t(2,t3);//将数转化为数组存储  
            len=1;  
            for(i=3;i<=99;i++)  
            {  
                jw=0;  
                for(j=1;j<=len;j++)    
                {  
                    temp=a[i-1][j]+a[i-2][j]+a[i-3][j]+jw;  
                    a[i][j]=temp%base;  
                    jw=temp/base;  
                    if(j==len && jw!=0)  
                        len++;  
                }  
            }  
        //  printf("[[[%d  %d  %d",a[0][0],a[0][]);  
            //while(a[99][len]==0)  
                //len--;  
            i=len;  
            printf("%d",a[99][i--]);  
            for(;i>=1;i--)  
                printf("%04d",a[99][i]);  
        }  
        printf("\n");  
    }  
    return 0;  
  
}

这是之前的代码不知道为什么提交老是不对，然后去讨论区看了一下，发现了错误，数组存大数时候，要考虑到0，如果是55500522每个数位存一个两位数的话，就会输出5550522，那个0被省略了；这次我改成这样了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>  
#include<string.h>  
#define base  100000000  
int a[100][100];  
void t(int i,int n)  
{  
    a[i][1]=n;  
}  
int main()  
{  
    //freopen("d:\\data\\1.txt","r",stdin);  
    int i,j,len,t1,t2,t3,temp,jw;  
    while(scanf("%d%d%d",&t1,&t2,&t3)!=EOF)  
    {  
        if(t1==0 && t2==0 && t3==0)  
            printf("0");  
        else  
        {  
            memset(a,0,sizeof(a));  
            t(0,t1);  
            t(1,t2);  
            t(2,t3);//将数转化为数组存储  
            len=1;  
            for(i=3;i<=99;i++)  
            {  
                jw=0;  
                for(j=1;j<=len;j++)    
                {  
                    temp=a[i-1][j]+a[i-2][j]+a[i-3][j]+jw;  
                    a[i][j]=temp%base;  
                    jw=temp/base;  
                    if(j==len && jw!=0)  
                        len++;  
                }  
            }  
        //  printf("[[[%d  %d  %d",a[0][0],a[0][]);  
            //while(a[99][len]==0)  
                //len--;  
            i=len;  
            printf("%d",a[99][i--]);  
            for(;i>=1;i--)  
                printf("%08d",a[99][i]);  
        }  
        printf("\n");  
    }  
    return 0;  
  
}

然后ac了，时间0，内存300+。

nyoj35 表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>  
#include<stdlib.h>  
#include<stack>  
using namespace std;  
stack<double> ovs;  
stack<char> ops;  
char s[1005];  
bool comp(char ,char);  
double calculate(double ,char ,double);  
int main()  
{  
    int N;  
    int i,j;  
    double num1,num2,ans;  
    char op;  
    scanf("%d",&N);  
    char w[100];  
    while(N--)  
    {  
        ops.push('#');  
        scanf("%s",s);  
        for(i=0;s[i]!='=';)//步长不写  
        {             
            if(s[i]>='0' && s[i]<='9')  
            {  
                j=0;  
                w[j++]=s[i++];  
                while((s[i]>='0' && s[i]<='9') || s[i]=='.')  
                {  
                    w[j++]=s[i++];  
                }  
                w[j]='\0';  
                ovs.push(atof(w));//如果是数字，则压入操作数栈  
                //printf("[ovs=%lf]\n",ovs.top());  
            }  
            else  
            {  
                if(comp(ops.top(),s[i]) || s[i]=='(')//如果是左括号或者运算符优先级高于top则压入运算符栈。  
                {  
                    ops.push(s[i]);  
                    i++;  
                }  
                else if(ops.top()=='(' && s[i]==')')//如果top和s[i]匹配，则运算符出栈  
                {  
                    ops.pop();  
                    i++;  
                }  
                else  
                {  
                    num2=ovs.top(); ovs.pop();//取出栈定元素运算                  
                    num1=ovs.top(); ovs.pop();                
                    op=ops.top(); ops.pop();                  
                    ovs.push(calculate(num1,op,num2));//再次压入栈。  
                }  
            }  
  
        }  
        //printf("size=%d\n",ovs.size());  
        while(ovs.size()!=1)//如果栈里运算数不是一个。则按顺序进行运算即可  
        {             
            num2=ovs.top(); ovs.pop();                
            num1=ovs.top(); ovs.pop();                
            op=ops.top(); ops.pop();              
            ovs.push(calculate(num1,op,num2));            
        }  
        printf("%.2lf\n",ovs.top());  
        while(!ovs.empty())//清空  
            ovs.pop();  
        while(!ops.empty())  
            ops.pop();  
    }  
    return 0;  
      
}  
bool comp(char op_top ,char op)//判断运算符优先级  
{  
    int top,_op;  
    switch(op_top)  
    {  
    case '*':  
    case '/':top=3;break;  
    case '+':  
    case '-':top=2;break;  
    case '(':  
    case ')':top=1;break;  
    case '#':top=0;break;  
    default :printf("1_error!\n");exit(1);  
    }  
    switch(op)  
    {  
    case '*':  
    case '/':_op=3;break;  
    case '+':  
    case '-':_op=2;break;  
    case '(':  
    case ')':_op=1;break;  
    case '#':_op=0;break;  
    default :printf("2_error!\n");exit(1);  
    }  
    return top<_op;  
}  
double calculate(double num1,char op,double num2)  
{  
    double ans;  
    switch(op)  
    {  
    case '*':ans=num1*num2;break;  
    case '/':ans=num1/num2;break;  
    case '+':ans=num1+num2;break;  
    case '-':ans=num1-num2;break;  
    default :printf("3_error!\n");exit(1);  
    }  
    return ans;  
}

nyoj1038 纸牌游戏

南阳oj第1038题：纸牌游戏
Accept代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
struct Pai  
{  
    char num;  
    char huase;  
};  
int comp(const void *a,const void *b)  
{  
    struct Pai *c=(Pai *)a;  
    struct Pai *d=(Pai *)b;  
    char cc=(c->huase=='H'?'U':c->huase);  
    char dd=(d->huase=='H'?'U':d->huase);  
    char ccc=c->num;  
    char ddd=d->num;  
    ccc=(ccc=='A'?'Z':ccc);  
    ccc=(ccc=='K'?'Y':ccc);   
    ccc=(ccc=='T'?'B':ccc);  
      
    ddd=(ddd=='A'?'Z':ddd);  
    ddd=(ddd=='K'?'Y':ddd);  
    ddd=(ddd=='T'?'B':ddd);  
    if(cc!=dd)  
        return cc-dd;  
    else  
        return ccc-ddd;  
}  
int main()  
{  
    //freopen("d:\\data\\1.txt","r",stdin);  
    //freopen("d:\\data\\2.txt","w",stdout);  
    struct Pai p[4][14];  
    char s1[150],s2[60];  
    char person;//先拿牌的人  
    int yu;  
    int i,j,t,k;  
    char shuxu[4][6]={"East","South","West","North"};  
    while(~scanf("%c",&person))  
    {  
        getchar();  
        scanf("%s",s1);  
        scanf("%s",s2);  
        getchar();  
        strcat(s1,s2);  
        switch(person)  
        {  
            case 'E':yu=0;break;  
            case 'S':yu=1;break;  
            case 'W':yu=2;break;  
            case 'N':yu=3;break;  
            default :printf("ohmygod\n");  
        }  
        for(i=0;i<4;i++)  
        {  
            t=0;  
            k=(i+yu)%4;  
            for(j=i*2;j<=103;j+=8)  
            {  
                p[k][t].num=s1[j];  
                p[k][t].huase=s1[j+1];  
                t++;  
            }  
            p[k][t].num='\0';  
            p[k][t].huase='\0';  
              
        }  
        for(i=0;i<4;i++)  
        {  
            printf("%s player:\n",shuxu[i]);  
            qsort(p[i],13,sizeof(p[i][0]),comp);  
            for(j=0;j<13;j++)  
                printf("+---+");  
            printf("\n");  
            for(j=0;j<13;j++)  
                printf("|%c %c|",p[i][j].num,p[i][j].num);  
            printf("\n");  
            for(j=0;j<13;j++)  
                printf("| %c |",p[i][j].huase);  
            printf("\n");  
            for(j=0;j<13;j++)  
                printf("|%c %c|",p[i][j].num,p[i][j].num);  
            printf("\n");  
            for(j=0;j<13;j++)  
                printf("+---+");  
            printf("\n");  
        }  
        printf("\n");  
              
    }     
    return 0;  
}

nyoj58 最少步数

这题明显是简单的DFS.
Accept代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<stdio.h>  
int p[9][9]={  
 1,1,1,1,1,1,1,1,1,  
 1,0,0,1,0,0,1,0,1,  
 1,0,0,1,1,0,0,0,1,  
 1,0,1,0,1,1,0,1,1,  
 1,0,0,0,0,1,0,0,1,  
 1,1,0,1,0,1,0,0,1,  
 1,1,0,1,0,1,0,0,1,  
 1,1,0,1,0,0,0,0,1,  
 1,1,1,1,1,1,1,1,1};  
int ans,cur;  
int x1,x2,y1,y2;  
int main()  
{  
    void dfs(int ,int,int);  
    int N;  
    scanf("%d",&N);  
    while(N--)  
    {  
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);  
        p[x1][y1]=1;  
        ans=100;  
        dfs(x1,y1,0);  
        printf("%d\n",ans);  
          
    }  
    return 0;  
}  
void dfs(int x1,int y1,int cur)  
{  
    if(x1==x2 && y1==y2)  
    {  
        ans=cur>ans?ans:cur;  
    }  
    if(x1<0 || x1>8 || y1<0 || y1>8)  
        return ;  
    if(!p[x1+1][y1]){ p[x1][y1]=1;  dfs(x1+1,y1,cur+1); p[x1][y1]=0;    }  
    if(!p[x1][y1+1]){ p[x1][y1]=1;  dfs(x1,y1+1,cur+1); p[x1][y1]=0;    }  
    if(!p[x1-1][y1]){ p[x1][y1]=1;  dfs(x1-1,y1,cur+1); p[x1][y1]=0;    }  
    if(!p[x1][y1-1]){ p[x1][y1]=1;  dfs(x1,y1-1,cur+1); p[x1][y1]=0;    }  
}