געפֿינען ווינער אויף אַ טיק טאַק טאָו שפיל לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן עפּל facebook זאָהאָ
מענגע

דער פּראָבלעם געפֿינען ווינער אויף אַ טיק טאַק טאָו שפּיל לעעטקאָדע סאַלושאַן פרעגט אונדז צו געפֿינען די געווינער פון אַ טיק טאַק פינגער פונ פוס שפּיל. דער פּראָבלעם גיט אונדז אַן מענגע אָדער וועקטאָר פון מאָוועס געמאכט דורך די פּלייַערס. מיר דאַרפֿן צו דורכפירן די מאָוועס און ריכטער ווער ווינס די שפּיל. די אַוטקאַם פון די שפּיל קענען זיין וואַן, ציען אָדער פּענדינג. אין קאַסעס, ווען איינער פון זיי ווינס די שפּיל, מיר צוריקקומען א אָדער ב. אָבער אויב איר ריכטער די שפּיל, מיר מוזן זיין אַווער פון די כּללים פון דעם ספּעציפיש ווערסיע פון ​​טיק טאַק טאָו.

  • פּלייַערס קענען בלויז מאַך אויף סקווערז וואָס האָבן נישט שוין געניצט.
  • דער ערשטער שפּילער A שטענדיק אָרט "X" אותיות, בשעת די רגע שפּילער B שטענדיק שטעלן "אָ" אותיות.
  • "X" און "O" אותיות זענען שטענדיק שטעלן אין ליידיק סקווערז. מען זאָל קיינמאָל נוצן סקווערז וואָס האָבן שוין יוטאַלייזד.
  • די שפּיל ענדס ווען עס זענען 3 פון די זעלבע (ניט-ליידיק) כאַראַקטער וואָס פּלאָמבירן קיין רודערן, זייַל אָדער דיאַגאָנאַל.
  • דער שפּיל אויך ענדס אויב אַלע סקווערז זענען ניט-ליידיק. אין עטלעכע פאלן, ביידע טאָן ניט געווינען און ענדיקן אין אַ ציען.
  • ניט מער באוועגט קענען ווערן געשפילט אויב די שפּיל איז איבער. אויב עס זענען עטלעכע מאָוועס לינקס, די ווערדיקט איז "פּענדינג".
  • פּלייַער "א" מאכט דער ערשטער מאַך, און דערנאָך די אַלטערנאַטיוו טורנס זענען געניצט דורך ביידע פּלייַערס.

לאָמיר נעמען עטלעכע ביישפילן.

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
"A"

געפֿינען ווינער אויף אַ טיק טאַק טאָו שפיל לעעטקאָדע סאַלושאַן

דערקלערונג: ווי געוויזן אויבן אין די פיגור, דער שפּילער מיט די "X" ווינס די שפּיל. א שטענדיק סטאַרץ די שפּיל, אַזוי דער געווינער איז אויך "א".

צוגאַנג צו געפֿינען ווינערז אויף אַ טיק טאַק טאָו שפּיל לעעטקאָדע סאַלושאַן

די פּראָבלעם איז צו געפֿינען די לעצט ווערדיקט פון די שפּיל טיק טאַק טאָו שפּיל נאָך עטלעכע מאָוועס. עס איז אַ נאָרמאַל שפּיל, אַזוי מיר דאַרפֿן צו סימולירן דעם פּראָצעס. מיר אויך דאַרפֿן צו דורכפירן די טריט אין דער זעלביקער סדר ווי געגעבן אין די אַרייַנשרייַב. איין וועג איז צו שאַפֿן אַ גריד פון 3 × 3 און סימולירן די זעלבע פּראָצעס. אָבער אַנשטאָט פון דאָס, מיר האַלטן שפּור פון מאָוועס געמאכט דורך ביידע פּלייַערס ניצן ערייז. מיר נוצן 4 פאַרשידענע ערייז פֿאַר ביידע פּלייַערס, 2 פֿאַר באוועגט דורך זיי וועגן יעדער רודערן און זייַל. פֿאַר יעדער מאַך מיר ינקראַמאַנץ די וואַלועס סטאָרד אין די ערייז. אַמאָל די וואַלועס ווערן גלייַך צו 3. מיר וויסן אַז 3 מאָוועס זענען געמאכט אָדער כאָריזאַנטאַלי אָדער ווערטיקלי.

פֿאַר דייאַגאַנאַלז, מיר פשוט נוצן 4 וועריאַבאַלז ענלעך צו ערייז. ווען איינער פון די ווערט ווערט גלייַך צו 3. מיר צוריקקומען די נאָמען אַקאָרדינגלי. אָבער אויב מיר טאָן ניט דערגרייכן אַ ווערדיקט ביז אַלע די מאָוועס זענען דורכגעקאָכט. דערנאָך מיר צוריקקומען אַ ווערדיקט פון די ציען אויב אַלע די סקווערז אויף די גריד זענען פאַרנומען, אַנדערש אויב די פּענדינג איז אומגעקערט.

קאָד פֿאַר געפינען ווינער אויף אַ טיק טאַק טאָו שפיל לעעטקאָדע סאַלושאַן

C ++ קאָד

#include <bits/stdc++.h>
using namespace std;

string tictactoe(vector<vector<int>>& moves) {
    int aRow[3] = {0}, bRow[3] = {0}, aCol[3] = {0}, bCol[3] = {0};
    int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
    int n = moves.size();
    for (int i = 0; i < n; i++) {
        int r = moves[i][0], c = moves[i][1];
        if (i % 2 == 1) {
            if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
        }else {
            if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
        }
    }
    return n == 9 ? "Draw" : "Pending";
}

int main(){
    vector<vector<int>> moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    cout<<tictactoe(moves);
}
A

Java קאָד

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String tictactoe(int[][] moves) {
        int[] aRow = new int[3];
        int[] aCol = new int[3];
        int[] bRow = new int[3];
        int[] bCol = new int[3];
        int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
        int n = moves.length;
        for (int i = 0; i < n; i++) {
            int r = moves[i][0], c = moves[i][1];
            if (i % 2 == 1) {
                if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
            }else {
                if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
            }
        }
        return n == 9 ? "Draw" : "Pending";        
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    	System.out.println(tictactoe(moves));
  }
}
A

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), וווּ N איז די נומער פון מאָוועס געשיקט ווי ינפּוט צו די פונקציע.

ספעיס קאַמפּלעקסיטי

אָ (ר + C), ווייַל מיר מאַכן 4 ערייז פון גרייס גלייַך צו די רודערן און זייַל פון די גריד אין טיק טאַק פינגער פונ פוס שפּיל.