d626: 小畫家真好用

https://zerojudge.tw/ShowProblem?problemid=d626

這一題在遞迴章節已經出現過了，但這題就是所謂的DFS，而這題的觀念延伸就可以實作下面一題 d365: 10336 - Rank the Languages

在遞迴函式中探索的方式

DFS概念

void 油漆桶擴散的DFS遞迴函式(int x,int y)
{
    if( x,y座標都沒超過邊界 且 a[x][y]剛好是空格)
    {
        1. 將a[x][y]上色
        2. call 油漆桶擴散的遞迴函式(x,y+1); 
        3. 另外還有其他三個方位，該怎麼做，想想看...
    }
}

解答

#include <bits/stdc++.h>
using namespace std;
int n=0;
char a[101][101];

void dfs(int x,int y)
{
    //此格子在地圖的範圍內，而且還沒有被上色
    if(x>=0&&y>=0&&x<=n&&y<=n&&a[x][y]=='-')
    {
        a[x][y]='+'; //上色
        dfs(x,y+1);  //往下方探索 ↓
        dfs(x,y-1);  //往上方探索 ↑
        dfs(x+1,y);  //往右方探索 →
        dfs(x-1,y);  //往左方探索 ←

    }
}

int main()
{

    int x,y;

    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];//輸入圖畫

    cin>>x>>y; //輸入倒油漆的位置

    dfs(x,y);//開始用油漆桶上色

    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<a[i][j];//輸出已經塗色的圖畫
        }
        cout<<endl;
    }

    return 0;

}