二維陣列應用範例

C++ 貪食蛇 : http://blog.xuite.net/eric10104/blog/30933328-C%2B%2B+%E8%B2%AA%E9%A3%9F%E8%9B%87%E9%81%8A%E6%88%B2%E8%A3%BD%E4%BD%9C

數獨 SudoKu : ( 二維陣列 + backtracking DFS )

數獨遊戲的玩法，是將數字1至9填在格子內，令到每一直行、橫行及每個小九宮格內，都有數字1至9，同時每個數字只可出現一次，不可重複。

#include <iostream>
using namespace std;
int len , map[10][10] , length ;
struct XD{
    int X , Y;    
};
XD point[100];
bool square[10][10] , flag;
int C ( int x , int y ){
    x = (x%len==0) ? x/len : x/len+1;
    y = (y%len==0) ? y/len : y/len+1;
    return (y-1) * len + x;
}
bool check( int x , int y , int number ){
    for ( int xx = 1 ; xx <= length ; xx++ )    
        if ( map[y][xx] == number )
            return 0;
    for ( int yy = 1 ; yy <= length ; yy++ )
        if ( map[yy][x] == number )
            return 0;
    int S = C ( x , y );
    if ( square[S][number] ) 
        return 0;
    return 1;
}
void DFS ( int left , int right ){
    if ( flag ) return;
    if ( left == right + 1 ){
        flag = 1;
        for ( int y = 1 ; y <= length ; y++ ){
            for ( int x = 1 ; x <= length ; x++ )
                printf("%d ",map[y][x]);        
            puts("");
        }
        return;
    }
    else{
        int x = point[left].X , y = point[left].Y;
        for ( int number = 1 ; number <= length ; number++ )
            if ( check( x , y , number ) ){
                int S = C(x,y);
                map[y][x] = number; square[S][number] = 1;
                DFS ( left+1 , right );
                map[y][x] = 0; square[S][number] = 0;
            }
    }
}
int main(){
    int r;
    while ( scanf("%d",&len) == 1 ){
        length = len * len; r = 0; flag = 0;
        memset ( square , 0 , sizeof(square) ); 
        for ( int y = 1 ; y <= length ; y++ )
            for ( int x = 1 ; x <= length ; x++ ){
                scanf("%d",&map[y][x]);
                if ( !map[y][x] ){
                    point[++r].X = x;     
                    point[r].Y = y;
                }
                int S = C ( x , y );
                if ( map[y][x] )
                square[S][map[y][x]] = 1;
            }
        bool run = 1;
        for ( int y = 1 ; y <= length && run; y++     )
            for ( int x = 1 ; x <= length ; x++ )
                if ( map[y][x] ){
                    int N = map[y][x]; map[y][x] = 0;
                    int S = C ( x , y ); square[S][N] = 0;
                    if ( !check( x , y , N ) ){    
                        run = 0;
                        break;
                    }
                    map[y][x] = N; square[S][N] = 1;
                }
        if ( run )
        DFS ( 1 , r );
        if ( !flag )
            printf("NO SOLUTION\n");
    }
    return 0;    
}

結果TLE

#include <bits/stdc++.h>

using namespace std;

int errorCount = 0;
int sudoku[9][9];

void check(int sx,int sy, int ex, int ey){

    int showTimes[9];
    for (int i = 0; i <=8; ++i){
      showTimes[i] = 0;
    }

    for(int x = sx; x<=ex;x++){
        for(int y = sy; y<=ey;y++){
                int number = sudoku[y][x];
                if(showTimes[number-1]>0){
                    errorCount++;
                    return;
                }else{
                    showTimes[number-1]++;
                }
        }
    }

}

int main(){

while(true){
    for(int i=0; i<9;i++){
        for(int j=0; j<9;j++){
            cin>>sudoku[i][j];
        }
    }

    errorCount=0;

    for ( int rows = 0 ; rows <=8 ; rows++ ){
        check(0,rows,8,rows);
    }

    for ( int cols = 0 ; cols <= 8 ; cols++ ){
        check(cols,0,cols,8);
    }

    check(0,0,2,2);
    check(3,0,5,2);
    check(6,0,8,2);

    check(0,3,2,5);
    check(3,3,5,5);
    check(6,3,8,5);

    check(0,6,2,8);
    check(3,6,5,8);
    check(6,6,8,8);

    if(errorCount>0){
        cout<<"no";
    }else{
        cout<<"yes";
    }
}
    return 0;
}