1

我试图解决 spoj 上的广度优先搜索问题。问题陈述如下：一个 n × n 方形单元阵列的等分是阵列中的 n^2 个单元在恰好 n 个集合中的分区，每个集合有 n 个连续的单元格。当两个单元具有共同的一侧时，它们是连续的。问题链接是：http ://www.spoj.com/problems/EQDIV/

我的代码：http: //ideone.com/OjluJG

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<queue>
using namespace std;
#define pii pair< int, int>
int n, m, grid[105][105];
char inp[101 * 101];

bool inRange(int i, int j)
{
    m = n;
    return (i >= 0 && i < n && j >= 0 && j < m);
}

int main()
{
    int i, j, comp;
    scanf("%d", &n);
    while (n != 0)
    {
        if (n == 1)
        {
            printf("good\n");
            scanf("%d", &n);
            continue;
        }
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                grid[i][j] = 0;
            }
        }
        int a, b, start1[n], start2[n], print = 0, c, d;
        queue< pii > Q;
        pii p;
        getchar();
        for (i = 1; i <= n - 1; i++)
        {
            gets(inp);
            stringstream ss(inp);
            for (j = 1; j <= n; j++)
            {
                ss >> a >> b;
                if (j == 1)
                {
                    start1[i - 1] = a;
                    start2[i - 1] = b;
                    //printf("%d %d\n",start1[i-1],start2[i-1]);
                }
                grid[a - 1][b - 1] = i;
            }
        }
        for (int x = 0; x < n; x++)
        {
            int count = 1;
            if (x == n - 1)
            {
                comp = 0;
                p.first = c;
                p.second = d;
                Q.push(p);
            }
            else
            {
                comp = x + 1;
                p.first = start1[x] - 1;
                p.second = start2[x] - 1;
                Q.push(p);
            }
            while (!Q.empty())
            {
                p = Q.front();
                i = p.first;
                j = p.second;
                Q.pop();
                grid[i][j] = -1;
                if (x != n - 1)
                {
                    if (inRange(i + 1, j) && grid[i + 1][j] == 0)
                    {
                        c = i + 1;
                        d = j;
                    }
                    if (inRange(i - 1, j) && grid[i - 1][j] == 0)
                    {
                        c = i - 1;
                        d = j;
                    }
                    if (inRange(i, j + 1) && grid[i][j + 1] == 0)
                    {
                        c = i;
                        d = j + 1;
                    }
                    if (inRange(i, j - 1) && grid[i][j - 1] == x + 1)
                    {
                        c = i;
                        d = j - 1;
                    }
                }

                if (inRange(i + 1, j) && grid[i + 1][j] == comp)
                {
                    p.first = i + 1;
                    p.second = j;
                    Q.push(p);
                    count += 1;
                }
                if (inRange(i - 1, j) && grid[i - 1][j] == comp)
                {
                    p.first = i - 1;
                    p.second = j;
                    Q.push(p);
                    count += 1;
                }
                if (inRange(i, j + 1) && grid[i][j + 1] == comp)
                {
                    p.first = i;
                    p.second = j + 1;
                    Q.push(p);
                    count += 1;
                }
                if (inRange(i, j - 1) && grid[i][j - 1] == comp)
                {
                    p.first = i;
                    p.second = j - 1;
                    Q.push(p);
                    count += 1;
                }
            }
            if (count != n)
            {
                print = 1;
                printf("wrong\n");
                break;

            }
        }
        if (print == 0)
            printf("good\n");
        //printf("%d %d\n",c,d);
        scanf("%d", &n);
    }
}

我得到错误的答案，不知道为什么？有人可以提供错误的测试用例吗？

4

0 回答 0