algorithm ccf-csp

CCF-CSP Questions (eight)

This is the second question of CCF-CSP in December 2013.

Posted by Dusign on 2019-06-29
Words 1.3k and Reading Time 7 Minutes
Viewed Times

Algorithms change the world. The importance of algorithms is self-evident to a programmer, so the practice of some algorithms is indispensable. Next, I will share some algorithmic problems.

Question

question

Analysis

Arrays or stacks can be used to store data, multiply and divide first, convert all operations into additions, and then add.

Solution

Here is the solution to this problem.The following are two solutions, the result is 100 points.

Program

Method One

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
//
//  main.cpp
//  ISBN
//
//  Created by gang du on 2019/6/29.
//  Copyright © 2019 gang du. All rights reserved.
//

#include<iostream>
#include<memory.h>
using namespace std;

#define LIM 50

int allDFS(char Map[LIM][LIM],bool sign[LIM][LIM],int startX,int startY,int row,int col,bool mark){
    if(mark==1){
        if((Map[startX][startY]=='S') || (Map[startX][startY]=='+') || (Map[startX][startY]=='T')){
            sign[startX][startY]=1;
            if(startX!=0 && sign[startX-1][startY]==0 && Map[startX-1][startY]!='#')
                allDFS(Map,sign,startX-1,startY,row,col,1);
            if((startX+1)!=row && sign[startX+1][startY]==0 && Map[startX+1][startY]!='#')
                allDFS(Map,sign,startX+1,startY,row,col,1);
            if(startY!=0 && sign[startX][startY-1]==0 && Map[startX][startY-1]!='#')
                allDFS(Map,sign,startX,startY-1,row,col,1);
            if((startY+1)!=col && sign[startX][startY+1]==0 && Map[startX][startY+1]!='#')
                allDFS(Map,sign,startX,startY+1,row,col,1); 
            return 0;
        }else if(Map[startX][startY]=='-'){
            sign[startX][startY]=1;
            if(startY!=0 && sign[startX][startY-1]==0 && Map[startX][startY-1]!='#')
                allDFS(Map,sign,startX,startY-1,row,col,1);
            if((startY+1)!=col && sign[startX][startY+1]==0 && Map[startX][startY+1]!='#')
                allDFS(Map,sign,startX,startY+1,row,col,1);
            return 0;
        }else if(Map[startX][startY]=='|'){
            sign[startX][startY]=1;
            if(startX!=0 && sign[startX-1][startY]==0 && Map[startX-1][startY]!='#')
                allDFS(Map,sign,startX-1,startY,row,col,1);
            if((startX+1)!=row && sign[startX+1][startY]==0 && Map[startX+1][startY]!='#')
                allDFS(Map,sign,startX+1,startY,row,col,1);
            return 0;
        }else if(Map[startX][startY]=='.'){
            sign[startX][startY]=1;
            if((startX+1)!=row && sign[startX+1][startY]==0 && Map[startX+1][startY]!='#')
                allDFS(Map,sign,startX+1,startY,row,col,1);
            return 0;
        }else{ 
            return 0;
        }
    }else{
        if(Map[startX][startY]!='#'){
            sign[startX][startY]=1;
            if(startX!=0 && sign[startX-1][startY]==0 && (Map[startX-1][startY]=='+' || Map[startX-1][startY]=='|' || Map[startX-1][startY]=='.' || Map[startX-1][startY]=='S' || Map[startX-1][startY]=='T'))
                allDFS(Map,sign,startX-1,startY,row,col,0);
            if((startX+1)!=row && sign[startX+1][startY]==0 && (Map[startX+1][startY]=='+' || Map[startX+1][startY]=='|' || Map[startX+1][startY]=='S' || Map[startX+1][startY]=='T'))
                allDFS(Map,sign,startX+1,startY,row,col,0);
            if(startY!=0 && sign[startX][startY-1]==0 && (Map[startX][startY-1]=='+' || Map[startX][startY-1]=='-' || Map[startX][startY-1]=='S' || Map[startX][startY-1]=='T'))
                allDFS(Map,sign,startX,startY-1,row,col,0);
            if((startY+1)!=col && sign[startX][startY+1]==0 && (Map[startX][startY+1]=='+' || Map[startX][startY+1]=='-' || Map[startX][startY+1]=='S' || Map[startX][startY+1]=='T'))
                allDFS(Map,sign,startX,startY+1,row,col,0); 
            return 0;
        }
        return 0;
    }
}

int main(){
	int row,col,i,j,sx,sy,ex,ey,num=0;
	bool fCanSearch[LIM][LIM],bCanSearch[LIM][LIM];
	char Map[LIM][LIM];	
	memset(fCanSearch,0,LIM*LIM);
	memset(bCanSearch,0,LIM*LIM);
	cin>>row>>col;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++){
			cin>>Map[i][j];
			if(Map[i][j]=='S'){
				sx=i;sy=j;
			}else if(Map[i][j]=='T'){
				ex=i;ey=j;
			}
		}
	allDFS(Map,fCanSearch,sx,sy,row,col,1);
	allDFS(Map,bCanSearch,ex,ey,row,col,0);
	if(fCanSearch[ex][ey]==0){
		cout<<"I'm stuck!"<<endl;
	}else{
		for(i=0;i<row;i++)
			for(j=0;j<col;j++){
				if(fCanSearch[i][j]==1 && bCanSearch[i][j]==0)
					num++;
			}
		cout<<num<<endl;
	}
	return 0; 
}

Method Two

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
//
//  main.cpp
//  ISBN
//
//  Created by gang du on 2019/6/29.
//  Copyright © 2019 gang du. All rights reserved.
//

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct P{
    int x,y;
};
char Map[55][55];
int mov[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
bool able[55][55][55][55],v1[55][55],v2[55][55];

void get(P a,int &st,int &ed){
    if(Map[a.x][a.y]=='-') st=2,ed=4;
    else if(Map[a.x][a.y]=='|') st=0,ed=2;
    else if(Map[a.x][a.y]=='.') st=0,ed=1;
    else st=0,ed=4;
}
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i) scanf("%s",Map[i]);
    queue<P> q;
    P p,e;
    for(i=0;i<n;++i)
    for(j=0;j<m;++j){
        if(Map[i][j]=='S'){
            p.x=i,p.y=j;
            q.push(p);
        }
        else if(Map[i][j]=='T'){
            e.x=i,e.y=j;
        }
    }
    memset(v1,0,sizeof(v1));
    memset(v2,0,sizeof(v2));
    memset(able,0,sizeof(able));
    v1[p.x][p.y]=1;
    while(!q.empty()){
        p=q.front();q.pop();
        P tem=p;
        int st,ed;
        get(p,st,ed);
        for(i=st;i<ed;++i){
            tem.x=p.x+mov[i][0];
            tem.y=p.y+mov[i][1];
            if(tem.x>=0&&tem.y>=0&&tem.x<n&&tem.y<m&&Map[tem.x][tem.y]!='#'){
                able[p.x][p.y][tem.x][tem.y]=1;
                if(!v1[tem.x][tem.y]){
                    v1[tem.x][tem.y]=1;
                    q.push(tem);
                }
            }
        }
    }
    if(!v1[e.x][e.y]) {puts("I'm stuck!");return 0;}
    int ans=0;
    q.push(e);
    v2[e.x][e.y]=1;
    while(!q.empty()){
        p=q.front();q.pop();
        P tem=p;
        for(i=0;i<4;++i){
            tem.x=p.x+mov[i][0];
            tem.y=p.y+mov[i][1];
            if(tem.x>=0&&tem.y>=0&&tem.x<n&&tem.y<m&&Map[tem.x][tem.y]!='#'&&able[tem.x][tem.y][p.x][p.y]&&!v2[tem.x][tem.y]){
                v2[tem.x][tem.y]=1;
                q.push(tem);
            }
        }
    }
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(v1[i][j]&&!v2[i][j]) ++ans;
    printf("%d\n",ans);
    return 0;
}

Remarks

This program is written in C++ and uses standard input and output functions.

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

...

00:00
00:00
FEATURED TAGS
algorithm ccf-csp
FRIENDS