题目描述

P1141 01迷宫

样例

C++ 代码

#include<iostream>
#include<algorithm>
//#include<stack>
#include<cstring> //memset
using namespace std;

const int N = 1010;
int cnt_m, cnt;
//stack<pair<int, int>> stk; //存储路径
char map[N][N];
bool st[N][N];   //passed: 1 , 可走: 0
int n, m;
int x_[4] = { 0, 0, -1, 1 };
int y_[4] = { -1, 1, 0, 0 };

bool jdg(int x, int y, char cc) //判断是否能走到(x,y), cc是原字符
{
    if (x < 1 || x > n || y < 1 || y > n) return false;   //out
    char c = map[x][y];
    if (c == cc)  return false;     //same char 
    if (st[x][y]) return false;     //passed 
    return true;
}

void dfs(int x, int y)
{
    char cc = map[x][y];

    if (!jdg(x, y + 1, cc) && !jdg(x, y - 1, cc) && !jdg(x + 1, y, cc) && !jdg(x - 1, y, cc))   // if 上下左右 unmovabel, then ...
    {  
        //cnt_m = max(cnt, cnt_m);
        //st[x][y] = 0;
        //if (map[x][y] == 's') cnt--;
        return;
    }

    // movable; 上下左右
    for (int i = 0; i < 4; i++)
    {
        if (jdg(x + x_[i], y + y_[i], cc))
        {
            cnt++;

            st[x + x_[i]][y + y_[i]] = 1;
            dfs(x + x_[i], y + y_[i]);
        }
    }
}

int main()
{
    cout.tie(0);     cin.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];

    while (m--) 
    {
        memset(st, 0, sizeof(st));
        /*for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                st[i][j] = 1;*/
        cnt = 0, cnt_m = 0;
        int x, y;
        cin >> x >> y;
        st[x][y] = 1;
        cnt++;
        dfs(x, y);
        cout << cnt << endl;
    }
    return 0;
}