深思熟虑之后,我觉得我不能再快乐地刷基础题了,两周之前自学了一个月的算法,再不刷都忘光了~本来就不咋会实现~

这是之前 2U 推荐我的题单,我终于要开始刷了┗|`O′|┛ 嗷

呜呜呜对我来说真的好难啊,不慌不慌,慢慢刷就是了唔...

从第一道题开始!
(/≧▽≦)/我第一道就弄了好久..

简单来说就是以n为边长的方形棋盘上有可以放棋的地方,但是任意两棋不在同行同列。问放k个棋的方法。
DFS回溯思想
其实不太知道回溯是干什么的,,,先用就是了。

代码在此

#include<iostream>
#include<string.h>
using namespace std;
char chess[10][10];
int visit[10];
int n,k,ans;

//x:第几行,y:已放置的棋子数 
void dfs(int x,int sum){
    if(sum >= k){
        ans ++ ;
        return;
    }
    if(x > n) return;
    for(int i = 0;i < n;i++){
        if(chess[x][i] == '#' && !visit[i]){
            visit[i] = 1;
            dfs(x+1,sum+1);
            visit[i] = 0;
        }
    }
    dfs(x+1,sum);
    return;
}

int main()
{
    while(cin>>n>>k && n != -1 && k != -1){
        
        memset(chess,0,sizeof(chess));
        memset(visit,0,sizeof(visit));
        
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                cin>>chess[i][j];
            }
        }
        ans = 0;
        dfs(0,0);
        cout<<ans<<endl;
    }    
} 

往下做嘛,第二道题从二维变成三维的了
我好不容易学会了怎么写,他就给我变样哼....

意思:给L片棋盘,棋盘的形状是R*C的,问从S道E的最短时间。
思路:应该用BFS,但是我DFS还没弄熟练,就这上面的题目先用了DFS,不过超时了。
首先,输入字符的时候,1.注意循环的内外侧(很基础但是一麻烦脑子就不灵光)2.每片棋盘都一行一行用%s输入。
其次,走六个方向的写法(这种题总会用到唔)

代码在此

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

char space[30][30][30];
int visit[30][30][30];
int xs,ys,zs,xe,ye,ze,L,R,C,ans,flag;

//6方位 
int s[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};

void dfs(int z,int x,int y,int step){
    //到终点 
    if(x == xe && y == ye && z == ze){
        ans = min(ans,step);
        flag = 1;
        return;
    }
    //从此点6位置dfs 
    for(int i = 0;i < 6;i++){
        int tmpx = x + s[i][0];
        int tmpy = y + s[i][1];
        int tmpz = z + s[i][2];
        
        /*判断是否界内*/ 
        if(tmpx < 0 || tmpx >= R || tmpy < 0 || tmpy >= C || tmpz < 0 || tmpz >= L) continue;
        
        if(space[tmpz][tmpx][tmpy] != '#' && !visit[tmpz][tmpx][tmpy]){
            visit[tmpz][tmpx][tmpy] = 1;
            dfs(tmpz,tmpx,tmpy,step+1);
            visit[tmpz][tmpx][tmpy] = 0;    //回溯 
        }
    }
    return;
}

int main()
{
    while(cin>>L>>R>>C && L && R && C){
        memset(space,0,sizeof(space));
        memset(visit,0,sizeof(visit));
        
        for(int z = 0;z < L;z++){
            for(int x = 0;x < R;x++){
                scanf("%s",space[z][x]);
                for(int y = 0;y < C;y++){
                    if(space[z][x][y] == 'S'){
                        xs = x;zs = z;ys = y;
                    }
                    if(space[z][x][y] == 'E'){
                        xe = x;ze = z;ye = y;
                    }
                }
            }
        }
        
        ans = 1000010;
        flag = 0;
        visit[zs][xs][ys] = 1;
        dfs(zs,xs,ys,0);
        
        if(flag) printf("Escaped in %d minute(s).\n",ans);
        else cout<<"Trapped!"<<endl;
    }
    return 0 ;
}

哎简单题做多了做这些要用脑子的题真要命呜呜呜。
但是每天两道题压力一点都不大,所以希望一后每天都能做两道,并且把前一天的重新做一遍呜呜呜。
这些让我敬畏却不能远之的题目啊!我什么时候能写明白
今天废话太多了,,,以后一定只写题。。。

(明天高数平时分测试啊,溜!!!)

Last modification:June 23rd, 2020 at 12:36 pm
请赏我杯奶茶,让我快乐长肉