题解 P1683 【入门】

梦里调音 · 2019-03-03 22:05:08 · 题解

题解前送大家一句话：

注意：瓷砖可以重复走过，但不能重复计数

如果你有什么感想，就别看题解了，改改代码吧。

一开始没看到这句话，我zz还用了回溯。

结果，只AC了一个点（算是给我面子）

真是：

审题不认真，代码两行泪

#include <bits/stdc++.h>
using namespace std;
int x[10000001],y[100000001],ans,sum,w,h,qx,qy;
char c[1001][1001];
bool flag[1001][1001];
int py[]={0,-1,0,1,0},px[]={0,0,1,0,-1};//上下左右 
int se(int sy,int sx){
//  cout<<sy<<" "<<sx<<endl;
    for(int i=1;i<=4;i++){
        ans=max(ans,sum);
        int dy=py[i]+sy,dx=px[i]+sx;
        if(flag[dy][dx]==0&&c[dy][dx]=='.'&&dy<=h&&dy>0&&dx<=w&&dx>0){
            flag[dy][dx]=1;
            sum++;
            se(dy,dx);
            flag[dy][dx]=0;
            sum--;
        }
    }
}
int main(){
    cin>>w>>h;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
            cin>>c[i][j];
            if(c[i][j]=='@')qx=j,qy=i;
        }
    sum++;
    flag[qy][qx]=1;
    se(qy,qx);
    cout<<ans<<endl;
    return 0;
}

这是该死的错误代码，欢迎拿走

正确代码：

哦对了，我是以第四象限建图的。

用bool标记；

走下步前先判断：

是否超界

是否走过（走过就不能计数了）

是否能走（即字符为‘.’）

#include <bits/stdc++.h>
using namespace std;
int x[10000001],y[100000001],ans,sum,w,h,qx,qy;
char c[1001][1001];
bool flag[1001][1001];
int py[]={0,-1,0,1,0},px[]={0,0,1,0,-1};//上下左右 
int se(int sy,int sx){
//  cout<<sy<<" "<<sx<<endl;
    for(int i=1;i<=4;i++){
        int dy=py[i]+sy,dx=px[i]+sx;
        if(flag[dy][dx]==0&&c[dy][dx]=='.'&&dy<=h&&dy>0&&dx<=w&&dx>0){
            flag[dy][dx]=1;
            sum++;
            se(dy,dx);
        }
    }
}
int main(){
    cin>>w>>h;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
            cin>>c[i][j];
            if(c[i][j]=='@')qx=j,qy=i;
        }
    sum++;
    flag[qy][qx]=1;
    se(qy,qx);
    cout<<sum<<endl;
    return 0;
}

请务必点赞，Thanks♪(･ω･)ﾉ